题目大意
每次在每个联通块中选一个点 \(u\)，删除这个点使得联通块分成若干个联通块，再从联通块中选点 \(v\)，在新树上连接 \(u,v\)，求新树叶节点的最大个数。
分析
易转化为求原树的最大独立集，设 \(f_{u,0/1}\) 为以 1 为根时不选/选 \(u\) 的最大独立集。显然有:
\[dp_{u,0}=\sum\limits_vmax(dp_{v,0/1})\\ dp_{u,1}=\sum\limits_vdp_{v,0}+1 \]手模第一个样例发现如果以原树的叶子为根节点时，可以同时选择相邻的点，要求以各节点为根的最大独立集，考虑换根 dp，设 \(g_{u,0/1}\) 为以 \(u\) 为根，不选/选 \(u\) 的最大独立集。显然有
\[g_{u,0}=max(g_{fa_u,1},f_{u,0}+g_{fa_u,0}-max(f_{u,0},f_{u,1})\\ g_{u,1}=f_{u,1}+g_{fa_u,0}-max(f_{u,0},f_{u,1})\]代码
void dfs(int u,int par){
f[u][0]=0,f[u][1]=1;
for(int v:G[u]){
if(v==par) continue;
dfs(v,u);
f[u][0]+=max(f[v][1],f[v][0]);
f[u][1]+=f[v][0];
}
}
void DFS(int u,int par){
ans=max(ans,max(g[u][1],g[u][0]+(G[u].size()==1)));
for(int v:G[u]){
if(v==par)
continue;
g[v][0]=max(g[u][1],f[v][0]+(g[u][0]-max(f[v][0],f[v][1])));
g[v][1]=f[v][1]+(g[u][0]-max(f[v][0],f[v][1]));
DFS(v,u);
}
}
void Main(){
n=rd;
for(int i=1;i<n;i++){
int u=rd,v=rd;
G[u].pb(v),G[v].pb(u);
}
dfs(1,0);
g[1][0]=f[1][0],g[1][1]=f[1][1];
DFS(1,0);
cout<<ans<<endl;
ans=0;
for(int i=1;i<=n;i++) G[i].clear();
}