solution

为根进行

表示以为根的子树中,是()否()选择了这个点,这个点是()否()被游览过的方案数。

答案就是

考虑如何转移。

对于,既然这个点没被游览过,那么他的儿子就肯定不能选择,而且因为没选这个点,所以他的儿子就不能通过选择来被游览,所以就只能从转移过来。

对于可以覆盖他的儿子,那么他的儿子是否被浏览过都可以,但是他的儿子不能被选择过,因为不可能有相邻的两个点被选择。所以就从转移过来。

对于,这个状态说明要被他的儿子覆盖,而他的儿子至少有一个要被选择,所以我们先从。转移,如果每个儿子都是从转移过来的,就再枚举一下让哪个儿子从转移。取最大的答案即可。

PS:看完别人写的题解,发现自己zz了,生生把2维状态能解决的事情设成了3维。。。

code

/*
* @Author: wxyww
* @Date:   2020-06-01 15:07:40
* @Last Modified time: 2020-06-01 16:15:36
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long ll;
const int N = 500010;
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1; c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0'; c = getchar();
    }
    return x * f;
}
int f[N][2][2];
struct node {
    int v,nxt;
}e[N << 1];
int head[N],ejs;

void add(int u,int v) {
    e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;
}

int n,S;
void dfs(int u,int fa) {
    f[u][1][1] = 1;
    int flag = 0;
    int ans = 0;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        dfs(v,u);
        f[u][1][1] += max(f[v][0][0],f[v][0][1]);
        f[u][0][0] += f[v][0][1];
        if(f[v][1][1] > f[v][0][1]) {
            flag = 1;
            ans += f[v][1][1];
        }
        else
            ans += f[v][0][1];
    }

    if(flag) {
        f[u][0][1] = ans;return;
    }

    int ret = 0;
    for(int i = head[u];i;i = e[i].nxt) {
        int v = e[i].v;
        if(v == fa) continue;
        ret = max(ret,ans - f[v][0][1] + f[v][1][1]);
    }
    f[u][0][1] = ret;

}
int main() {
    n = read();S = read();

    for(int i = 1;i < n;++i) {
        int u = read(),v = read();
        add(u,v);add(v,u);
    }

    dfs(S,0);
    cout<<f[S][1][1];
    return 0;
}