NC201400 树学_牛客博客

引言

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

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

题解

暴力

这道题有一个显然的 $O(n^2)$ 的暴力思路：就是枚举每一个点作为根，扫一遍。

换根DP

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

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

显然，想要 $O(1)$ 转移这两个根 $x,y$ 的信息，他们必定在树上相邻。

观察上面的这张图

假设当前 $x$ 为根，向 $y$ 换根时，有 $n - size_y$ 的点距离增加一，有 $size_y$ 个点距离减少一。

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

关于本题的特殊做法

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

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

关于换根 DP

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

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

换根 DP 的核心就在于从 $x$ 变为 $y$ 为根的时候，它们的参数大多相同，或变化有规律（且这种规律能够在很低的复杂度被转移和维护），在这种情况下，换根 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;
}