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; }