【ICPC】2022 昆明站 F题 题解

题目大意

给定一个 n n n个节点的树，每个点有个权值 b i b_i bi​,任选一条路径，路径上的点至少为 2 2 2个。求 m a x ( ∑ − x 2 + b k x v ) max(\sum\frac{-x^2+b_kx}{v}) max(∑v−x2+bk​x​),其中 b k b_k bk​是路径上点的权值， v v v是路径上点的个数， x x x是任意一个自己选择的数。

题目链接

思路

假如 b v b_v bv​确定了，它是一个一元二次方程， x x x是自变量，最大值为 ∑ b k 2 4 v 2 \sum \frac{b_k^2}{4v^2} ∑4v2bk2​​,那么我们只需要最大化 ∣ ∑ b k v ∣ |\sum \frac{b_k}{v}| ∣∑vbk​​∣

即，在树上找一条路径，使得路径上平均权值最大。

一个定理:一段序列，连续取数的话，构成平均值最大数，最多不超过 3 3 3个。
题目要求至少为两个点，假如我们超过了 4 4 4个点，我们可以把它分成两个 2 2 2段，取大的，那么平均值就会变大。
（为什么 3 3 3个不能分？因为两个数的平均值可能比那个单个的数小，即中间的数比较小，两边的数比较大，比如3,2,3）。

所以我们只要找到每个点相连的点中，最大值，次最大值。
另外需要注意的是，我们是最大化 ∣ ∑ b k v ∣ |\sum \frac{b_k}{v}| ∣∑vbk​​∣，而权值可能为负数，所以最小值，次最小值也要存下来。

最后依次遍历，求得最大值。

代码

#include 
#include 
#include 
#include 
using namespace std;

const int maxN = 1e5 + 7;
int n, a[maxN];
double avg;
vector<int> g[maxN];

bool cmp(int x, int y)
{
    return a[x] > a[y];
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i < n; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
        avg = max(avg, (double)(a[x] + a[y]) * (a[x] + a[y]) / 16);
    }
    for(int i = 1; i <= n; ++i)
        sort(g[i].begin(), g[i].end(), cmp);
    for(int i = 1; i <= n; ++i) 
        if(g[i].size() >= 2) {
            avg = max(avg, (double)(a[i] + a[g[i][0]] + a[g[i][1]]) * (a[i] + a[g[i][0]] + a[g[i][1]])/ 36);
            avg = max(avg, (double)(a[i] + a[g[i][g[i].size() - 1]] + a[g[i][g[i].size() - 2]]) * (a[i] + a[g[i][g[i].size() - 1]] + a[g[i][g[i].size() - 2]]) / 36);
        }
    printf("%lf\n", avg);
    return 0;
}