You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

70 lines
2.3 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 200010, M = N << 1;
int n;
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int sz[N]; // sz[i]:以i为根的子树中有多少个节点
int f[N];
int g[N];
int ans; // 答案
// 以子填父
void dfs1(int u, int fa) {
sz[u] = 1; // 以u为根的子树最起码有u自己1个节点
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs1(v, u); // 换根dp的套路第一次 dfs,以子填父,先递归,后累加
sz[u] += sz[v]; // 将儿子节点v子树的节点数量累加到u子树上
f[u] += f[v]; // 权值也需要累加
}
f[u] += sz[u]; // 别忘了加上自己子树的个数之所以放在这里写是因为需要所有子树递归完成统计后才有sz[u]
}
// 换根dp
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue; // 填充g[]数组的权值最大值
// 此处 sz[1]=n,怎么写都行
g[v] = n + g[u] - 2 * sz[v]; // 数学方法计算出来修改v的最终答案
// 自顶向下修改统计信息,统计信息是指以每个点为根时可以获取到的最大权值
dfs2(v, u);
}
}
signed main() {
// 初始化链式前向星
memset(h, -1, sizeof h);
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
// 第一次dfs,以子孙节点信息更新父节点的统计信息统计信息包括以u为根的子树中节点数个sz[u],每个节点可以获取到的权值f[u]
dfs1(1, 0);
// f[i]:以1为根时的, 以i为子树根的子树可以获得的最大权值
// g[i]:以i为根的子树可以获得的最大权值,也就是最终的结果存储数组
g[1] = f[1];
// 第二次dfs,换根
dfs2(1, 0);
// 遍历一遍历,找出到底以谁为根可以获取到权值的最大值,最大值是多少
for (int i = 1; i <= n; i++) ans = max(ans, g[i]);
// 输出答案
cout << ans << endl;
}