NC201400 树学

引言

对于树上的题目，一般都是在搜的过程中 解决。

其中 为搜索函数的复杂度。

题解

暴力

这道题有一个显然的 的暴力思路：就是枚举每一个点作为根，扫一遍。

换根DP

分析暴力做法的时间复杂度瓶颈，发现主要在于每次都要遍历整棵树。

考虑是否能够每次 地转移两个根之间的信息。

显然，想要 转移这两个根 的信息，他们必定在树上相邻。

观察上面的这张图

假设当前 为根，向 换根时，有 的点距离增加一，有 个点距离减少一。

先钦定 为根，把 dep 都跑出来，然后再次遍历的过程中取 max 就行了。

关于本题的特殊做法

这个题好像是牛客OI周赛14普及的第三题

由于点权的特殊性，只需要写个树的重心

关于换根 DP

这题是换根 DP 最入门的题目。

换根 DP 的暴力一般是二次方或三次方基本的。

换根 DP 的核心就在于从 变为 为根的时候，它们的参数大多相同，或变化有规律（且这种规律能够在很低的复杂度被转移和维护），在这种情况下，换根 DP 就可以在线性复杂度下完成问题求解。

Code

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 1000000 + 7;
const int maxm = 2000000 + 7;
const int INF = 0x3f3f3f3f;

int n, m;

#define Graph_Define
#ifdef Graph_Define
int Head[maxn], to[maxm], Next[maxm], tot;

void addedge(int x, int y) {
    to[++tot] = y, Next[tot] = Head[x], Head[x] = tot;
}
void add(int x, int y) {
    addedge(x, y);
    addedge(y, x);
}
#endif

template < typename Tp >
void read(Tp &x) {
    x = 0;char ch = 1;int fh = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch=getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

void Init(void) {
    read(n);
    for(int i = 1, x, y; i < n; i++) {
        read(x); read(y);
        add(x, y);
    }
}

int dep[maxn], size[maxn], sum[maxn];

void dfs1(int x, int f, int dp) {
    size[x] = 1, dep[x] = dp, sum[x] += dp;
    for(int i = Head[x]; i; i = Next[i]) {
        int y = to[i];
        if(y == f) continue;
        dfs1(y, x, dp + 1);
        size[x] += size[y], sum[x] += sum[y];
    }
}

int ans = INF;

void dfs2(int x, int f, int val) {
    ans = min(ans, val);
    for(int i = Head[x]; i; i = Next[i]) {
        int y = to[i];
        if(y == f) continue;
        dfs2(y, x, val + n - size[y]  - size[y]);
    }
}

void Work(void) {
    dfs1(1, 0, 0);
    dfs2(1, 0, sum[1]);
    printf("%d\n", ans);
}

int main() {
    Init();
    Work();
    return 0;
}