Luogu 3478 [POI2008]STA-Station

题目链接：​​传送门​​

题目描述

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

输入样例

8
1 4
5 6
4 5
6 7
6 8
2 4
3 4

输出样例

7

一句话题意
好吓人啊
其实还是很简单的
设表示以为根能获得深度和
那么如果我们选了的任意一个儿子节点
那么以为根节点的所有点的深度都会减一
也就是
所有不是的子树的点深度都加一
那就是
要用f[i]加上它们两个
就是
递推式出来了
这题做完了
要记得预处理的情况
就是以为根的时候的深度和
这题需要

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node{
    int next, to;
}edge[A];
int head[A], num_edge;
void add_edge(int from, int to) {
    edge[++num_edge].next = head[from];
    edge[num_edge].to = to;
    head[from] = num_edge;
}
int n, m, a, b, rank;
ll f[A], ans, dep[A], siz[A];
void prepare(int fr, int fa) {
    siz[fr] = 1; dep[fr] = dep[fa] + 1;
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa) continue;
        prepare(ca, fr);
        siz[fr] += siz[ca];
    }
}
void dfs(int fr, int fa) {
    for (int i = head[fr]; i; i = edge[i].next) {
        int ca = edge[i].to;
        if (ca == fa) continue;
        f[ca] = f[fr] + n - siz[ca] * 2;
        dfs(ca, fr);
    }
}

int main(int argc, char const *argv[])
{
    cin >> n;
    for (int i = 1; i < n; i++) {
        cin >> a >> b;
        add_edge(a, b);
        add_edge(b, a);
    }
    prepare(1, 0);
    for (int i = 1; i <= n; i++) f[1] += dep[i];
    dfs(1, 0);
    for (int i = 1; i <= n; i++)
        if (f[i] > ans)
            ans = f[i], rank = i;
    cout << rank;
    return 0;
}