首页 > 其他 > 详细

cf219d 基础换根法

时间:2019-01-30 10:42:00      阅读:239      评论:0      收藏:0      [点我收藏+]
/*树形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<<" ";  
}

 

cf219d 基础换根法

原文:https://www.cnblogs.com/zsben991126/p/10336970.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!