NC15748

题意：
给定一棵 n 个节点的树，初始选择节点 s，第一天定居在s，并将s和与s相邻的节点染色。之后每一天选择一个未染色的点定居，将定居点和定居点相邻的节点染色。问最多能定居多少个节点。

题解
每个点都会被染***r>考虑如何给叶子节点染色，发现要把叶子节点染色，定居在叶子处最佳，所以我们首先选择叶子节点定居。染色后把染色的点去掉，给新的叶子染色，直到所有节点被染色。

Code

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int maxn = 5e5 + 101;
const int mod=1024523;
int n,s;
vector<int>g[maxn];
bool vis[maxn];
int ans=1;
void dfs(int u,int fa){
    for(auto to:g[u]){
        if(to==fa||vis[to]) continue;
        dfs(to,u);
    }
    if(!vis[u]){
        vis[u]=true;vis[fa]=true;ans++;
    }
}

int main(){
    read(n);read(s);
    fo(i,1,n-1){
        int u,v;read(u);read(v);
        g[u].push_back(v);g[v].push_back(u);
    }
    vis[s]=true;
    for(auto to:g[s]){
        vis[to]=true;
        dfs(to,s);
    }
    printf("%d\n",ans);
    return 0;
}