NC15748

感受
巨水@_@

思路
最开始的思路比较暴力，直接从s出发然后干掉距离小于等于1的点，对于剩下的点构成很多连通块，我们只需求所有连通块的最大独立集合的和即可。有点懒，然后就用DP实现了。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 500000 + 10;
struct edge{
    int v, nex;
}e[maxn << 1];
int n, head[maxn], cnt, s, dp[maxn][2];
void add_edge(int u, int v){
    e[cnt] = (edge){v, head[u]};
    head[u] = cnt++;
}
void dfs(int u, int f){
    int dp0 = 0, dp1 = 1;
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(v == f) continue;
        dfs(v, u);
        dp0 += max(dp[v][0], dp[v][1]);
        dp1 += dp[v][0];
    }
    dp[u][0] = dp0; dp[u][1] = dp1;
}
int main(){
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &s);
    int u, v;
    for(int i = 1; i < n; i++){
        scanf("%d%d", &u, &v);
        add_edge(u, v); add_edge(v, u);
    }
    dfs(s, 0);
    printf("%d\n", dp[s][1]);
    return 0;
}