题解 | #旅游#

本质上就是一个 没有上司的舞会。

不能同时选相邻的两个点，另外根结点必选，直接考虑套 没有上司的舞会 的模板即可：

• $f[u]f[u]$ 表示 $uu$ 必选，以 $uu$ 为根的子树的答案；
• $g[u]g[u]$ 表示 $uu$ 不选，以 $uu$ 为根的子树的答案；

$f[u]\leftarrow g[v]f[u]\backslash leftarrow\; g[v]$，$uu$ 选了儿子 $vv$ 一定不能选；

$g[u]\leftarrow \max \{f[v],g[v]\}g[u]\backslash leftarrow\backslash max\backslash \{f[v],g[v]\backslash \}$，$uu$ 不选，儿子 $vv$ 可选可不选。

#include<cstdio>
#include<vector>
int init(){
	char c = getchar();
	int x = 0, f = 1;
	for (; c < '0' || c > '9'; c = getchar())
		if (c == '-') f = -1;
	for (; c >= '0' && c <= '9'; c = getchar())
		x = (x << 1) + (x << 3) + (c ^ 48);
	return x * f;
}
void print(int x){
	if (x < 0) x = -x, putchar('-');
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int N = (int) 5e5 + 5;
std::vector<int>G[N];
void add(int u, int v){
    G[u].push_back(v), G[v].push_back(u);
}
int f[N], g[N];
int mx(int x, int y){
    return x > y ? x : y;
}
void dfs(int u, int fa){
    int Len = G[u].size();
    f[u] = 1;
    for (int i = 0; i < Len; ++i) {
        int v = G[u][i];
        if (v == fa) continue;
        dfs(v, u);
        f[u] += g[v];
        g[u] += mx(f[v], g[v]);
    }
}
int main(){
	int n = init(), s = init();
	for (int i = 1; i < n; ++i)
		add(init(), init());
	dfs(s, s);
    print(f[s]), putchar('\n');
}