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;
}
------ 本文结束 ------