cf219d 基础换根法

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

 

转载于:https://www.cnblogs.com/zsben991126/p/10336970.html