【ICPC】2022 昆明站 F题 题解

题目大意

给定一个 $n$ 个节点的树，每个点有个权值 $b_i$，任选一条路径，路径上的点至少为 $2$ 个。求

$$\max\left(\sum\frac{-x^2+b_kx}{v}\right)$$

其中 $b_k$ 是路径上点的权值，$v$ 是路径上点的个数，$x$ 是任意一个自己选择的数。

题目链接

思路

以 $x$ 为自变量，最大值为 $\dfrac{(\sum b_k)^2}{4v^2}$，正比于 $\left|\dfrac{\sum b_k}{v}\right|$。

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

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

所以我们只要找到每个点相连的点中，最大值和次最大值。

另外需要注意的是，我们是最大化 $\left|\dfrac{\sum b_k}{v}\right|$。

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

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
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;
}