2022ICPC昆明F

2022ICPC昆明F

题目链接
  不难看出最终答案为/((sum/num)^2/4/)。问题转化为在树上找到一条简单路径，使得路径点权和除以点数绝对值最大。
  考虑二分，二分出平均值并在树上/(dp/)处理。在此清华大学赛时代码使用了预处理树后续遍历的方式解决了此题，不仅避免了树形/(dp/)搜索途中的/(for/)循环嵌套与重复递归调用，更是大大增加了代码可读性：

vector<int> vs;
void dfs0(int x, int f = 0) {
    fa[x] = f;
    for(auto v :g[x]) if(v != f) {
        dfs0(v, x);
    }
    vs.push_back(x);//创建序列
}
 
bool calc(double V) {
    for(auto x : vs) {
        for(auto v : g[x]) if(v != fa[x]) {
            //do something
        }
    }
    if(pd) return true;
    else return false;
}

回到本题，题目中特别强调了简单路径长度大于/(1/)，那么在维护/(dp/)时需要特别注意：我们不能用可能为单独点集的情况更新/(ans/)。在此可以用树上背包的常用方式——/(x/)为根的子树会逐渐增加大小，在更新答案后再更新背包大小。在此题中可以先更新/(ans/)再更新/(dp/)值做到。在此/(dp[x]/)为以/(x/)为根的最长路径，/(ans[x]/)为以/(x/)为根的子树答案。

#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#define Lint long long
#define pi acos(-1.0)
using namespace std;
const int N = 1e5 + 10;
int n, f[N];
double a[N], dp[N], ans[N];
vector<int> v[N], s;
void dfs(int x, int fa)
{
    f[x] = fa;
    for (auto i : v[x])
    {
        if (i == f[x])
            continue;
        dfs(i, x);
    }
    s.push_back(x);
}
bool check(double x)
{
    for (auto i : s)
    {
        ans[i] = -1e9;
        dp[i] = a[i] - x;
        if (v[i].size() == 1 && f[i])
        {
            ans[i] = -1e9;
            dp[i] = a[i] - x;
        }
        else
        {
            for (auto j : v[i])
            {
                if (j == f[i])
                    continue;
                ans[i] = max(dp[i] + dp[j], ans[i]);
                dp[i] = max(dp[i], dp[j] + a[i] - x);
                ans[i] = max(ans[i], ans[j]);
            }
        }
    }
    if (ans[1] >= 0)
        return true;
    return false;
}
void solve()
{
    int x, y;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &a[i]);
    for (int i = 1; i < n; ++i)
    {
        scanf("%d%d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    double l = 0, r = 100000;
    double ans = 0.0;
    for (int i = 1; i <= 50; ++i)
    {
        double mid = (l + r) / 2.0;
        if (check(mid))
        {
            ans = mid;
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    for (int i = 1; i <= n; ++i)
        a[i] = -1 * a[i];
    l = 0, r = 100000;
    for (int i = 1; i <= 50; ++i)
    {
        double mid = (l + r) / 2.0;
        if (check(mid))
        {
            ans = max(ans, mid);
            l = mid;
        }
        else
        {
            r = mid;
        }
    }
    printf("%.10lf/n", ans * ans / 4.0);
}
int main()
{
    // cin.tie(0);
    // cout.tie(0);
    // ios::sync_with_stdio(0);
    solve();
    return 0;
}

此写法复杂度为/(O(nlogn)/)，虽然复杂度完全正确但由于牛客评测机严重波动问题使其运行速度在/(400ms/)到/(TLE/)不等。标程证明了点的选择数目为/(2/)或/(3/)个，在此给出队友的简要证明：任意一个大于/(3/)的点集都可被分组为两个大于等于/(2/)的点集，在此之中必然存在一个点集使得平均值大于等于原点集，选择此小点集答案必然更优。复杂度为/(O(n)/)。