题意：有1-n个点由n-1条边连接起来，第一晚住在s点，并游览s相邻的点，第二晚住在除了s和游览过的点以外的点，以此类推，问能住几晚
Solution
很模板的树形dp
dp[i][0/1]表示在i点是否住下的答案
如果不在i点住，那么相邻的点住不住都行，即dp[pos][0]+=max(dp[next][0],dp[next][1])
如果在i点住，那么相邻的点不能住，dp[pos][1]+=dp[next][0]
1 void dfs(int pos,int x) 2 { 3 dp[pos][0]=0; 4 dp[pos][1]=1; 5 for(auto it:e[pos]) 6 { 7 if(it==x)continue; 8 dfs(it,pos); 9 dp[pos][0]+=max(dp[it][1],dp[it][0]); 10 dp[pos][1]+=dp[it][0]; 11 } 12 } 13 14 void solve() 15 { 16 int n,s;cin>>n>>s; 17 18 for(int i=1;i<=n-1;i++) 19 { 20 int u,v;cin>>u>>v; 21 e[u].push_back(v); 22 e[v].push_back(u); 23 } 24 dfs(s,0); 25 cout<<dp[s][1]<<"\n"; 26 27 }