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.

64 lines
2.1 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;
const int N = 1000010, M = N << 1;
#define int long long
#define endl "\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 n; // n个节点
int depth[N]; // depth[i]:在以1号节点为根的树中i号节点的深度是多少
int sz[N]; // sz[i]:以i号节点为根的子树中有多少个节点
int f[N]; // DP结果数组f[i]记录整个树以i为根时可以获取到的深度和是多少
// 第一次dfs
void dfs1(int u, int fa) {
sz[u] = 1; // 以u为根的子树最起码有u一个节点
depth[u] = depth[fa] + 1; // u节点的深度是它父节点深度+1
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
dfs1(v, u); // 深搜v节点,填充 sz[v],depth[v]
sz[u] += sz[v]; // 在完成了sz[v]和depth[v]的填充工作后利用儿子更新父亲的sz[u]+=sz[v];
}
}
// 第二次dfs
void dfs2(int u, int fa) {
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
if (v == fa) continue;
f[v] = f[u] + n - 2 * sz[v];
dfs2(v, u);
}
}
signed main() {
memset(h, -1, sizeof h); // 初始化链式前向星
cin >> n;
for (int i = 1; i < n; i++) { // n-1条边
int a, b;
cin >> a >> b;
add(a, b), add(b, a); // 换根DP无向图
}
// 1、第一次dfs,以1号节点为根它的父节点不存在传入0
dfs1(1, 0);
// 2、换根
for (int i = 1; i <= n; i++) f[1] += depth[i]; // DP初始化以1号节点为根时所有节点的深度和
dfs2(1, 0); // 从1号节点开始深度进行换根
// 3、找答案
int ans = 0, id = 0;
for (int i = 1; i <= n; i++) // 遍历每个节点
if (ans < f[i]) ans = f[i], id = i; // ans记录最大的深度值id记录以哪个节点为根时取得最大值
// 输出以哪个节点为根时,深度和最大
cout << id << endl;
}