cf219d 基础换根法

时间:2021-11-05 12:16:59
/*树形dp换根法*/
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
struct Edge{int to,nxt,flag;}edge[maxn<<];
int root,n,s,t,head[maxn],tot,dp[maxn];
void init(){
memset(head,-,sizeof head);
tot=;
}
void addedge(int u,int v,int flag){
edge[tot].to=v;edge[tot].nxt=head[u];edge[tot].flag=flag;
head[u]=tot++;
}
void dfs1(int u,int pre){
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v==pre)continue;
if(edge[i].flag==)dp[u]++;
dfs1(v,u);
dp[u]+=dp[v];
}
}
void dfs2(int u,int pre){
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
dp[v]=dp[u]+(edge[i].flag==?:-);
if(v==pre)continue;
dfs2(v,u);
}
}
int main(){
init();
cin>>n;
for(int i=;i<n;i++){
cin>>s>>t;
addedge(s,t,);
addedge(t,s,);
}
root=;
dfs1(,);//第一次dfs求出dp[1]
dfs2(,);//第二次dfs求出剩下的结点
int ans=;
for(int i=;i<=n;i++)ans=min(ans,dp[i]);
cout<<ans<<endl;
for(int i=;i<=n;i++)
if(dp[i]==ans)cout<<i<<" ";
}