Codeforces 1092F (树形DP(二次扫描换根))

Codeforces 1092F
题意：给定一棵有$n$个节点的树，给定每个点的点权，每个边的边权是$1$。你可以任选一个点作为$v$点，使得$\sum_{i=1}^n{dist(i,v) \cdot a_i}$最大。输出这个最大值。

二次扫描换根模板题。
显然是一个无根树最优化问题，那么逃不了DP。所以就是先随便找一个根DP一次，然后通过 DFS 再将推导出其他的答案。
本题显然能进行推导，若$v$是$u$的孩子，则

$$
\sum_{i \in 子树u}{dist(i,u) \cdot a_i}=\sum_{i \in 子树v}{(dist(i,v) +1) \cdot a_i}=\sum_{i \in 子树v}{dist(i,v) \cdot a_i+a_i}=\sum_{i \in 子树v}{dist(i,v) \cdot a_i+\sum_{i \in 子树v}a_i}
$$

设$sum(u)=\sum_{i \in 子树u}a_i$，那么$u$可以从$v$推导而来。

对于换根可以利用二次扫描换根知识和推推公式算出最后的答案。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 200000 + 5;

    int n, a[MAXN];
    vector<int > G[MAXN];
    LL sum[MAXN], g[MAXN], f[MAXN];

    void ins(int x, int y) {G[x].push_back(y);}

    void dfs1(int u, int fa) {
        sum[u] = a[u];
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) dfs1(v, u), sum[u] += sum[v], g[u] += g[v] + sum[v];
        }
    }
    void dfs2(int u, int fa) {
        for (int i = 0; i < (int)G[u].size(); ++i) {
            int v = G[u][i];
            if (v != fa) {
                f[v] = f[u] - sum[v] + (sum[1] - sum[v]); // 前提是已经算出父亲，所以先算再 dfs 
                dfs2(v, u);
            }
        }
    }

    void clean() {
        ms(sum, 0), ms(g, 0), ms(f, 0);
    }
    int solve() {
        clean();
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int x, y, i = 1; i < n; ++i) scanf("%d%d", &x, &y), ins(x, y), ins(y, x);
        dfs1(1, 0);
        f[1] = g[1], dfs2(1, 0);
        LL ans = 0ll;
        for (int i = 1; i <= n; ++i) ans = max(ans, f[i]);
        printf("%lld\n", ans);
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}