洛谷 P3478 POI 2008 STA-Station

url: https://www.luogu.com.cn/problem/P3478

tag:
树形DP，POI，2008

思路：
利用两次dfs，第一次求出以1为根节点时深度和，以及各个节点为根时的子树大小，之后利用第二次dfs求出每个节点为根时的深度和。这个方法称为二次扫描。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int h[N], e[N * 2], ne[N * 2], idx;
int n;
long long res, id;
long long d[N], s[N], f[N];
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void dfs(int u, int fa)
{
    s[u] = 1; d[u] = d[fa] + 1;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfs(j, u);
        s[u] += s[j];
    }
}

void dfs2(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        f[j] = f[u] + n - 2 * s[j];
        dfs2(j, u);
    }
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i ++) f[1] += d[i];
    dfs2(1, 0);
    for (int i = 1; i <= n; i ++) if (f[i] > res) res = f[i], id = i;
    cout << id << endl;
    return 0;
}