JZOJ【NOIP2015模拟11.4】统一天下

【思路】

将两棵树重心相连，做树形DP

易得

Down[now]=∑Down[son]+Size[son]

Up[son]=Up[now]+Size[1]-Size[son]*2+Down[now]-Down[son]

初始化：Up[1]=0

【注意事项】

1.部分数据在JZ的辣鸡电脑上跑会爆栈，交到OJ就可以了

2.什么？你不会求重心？

https://oi-wiki.org/graph/tree-centroid/

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<string>
  5 #include<cstring>
  6 using namespace std;
  7 int n1,n2,m,h[300005],g[300005],wd[600005],c[6000005],dis[600005];
  8 int wnt,cnt,tot,rt1,rt2,wt[300005],size[600005],fa[600005];
  9 int x1[600005],x2[600005],y1[600005],y2[600005];
 10 long long up[6000005],down[6000005];
 11 long long ans;
 12 struct node
 13 {
 14     int next,to;
 15 }e[6000005],f[6000005],w[2000005];
 16 void add(int x,int y)
 17 {
 18     e[++cnt].to=y;
 19     e[cnt].next=h[x];
 20     h[x]=cnt;
 21 }
 22 void odd(int x,int y)
 23 {
 24     f[++tot].to=y;
 25     f[tot].next=g[x];
 26     g[x]=tot;
 27 }
 28 void add_edge(int x,int y)
 29 {
 30     w[++wnt].to=y;
 31     w[wnt].next=wd[x];
 32     wd[x]=wnt;
 33 }
 34 void get1(int x,int fa)
 35 {
 36     size[x]=1;
 37     wt[x]=0;
 38     for(int i=h[x];i;i=e[i].next)
 39     {
 40         int y=e[i].to;
 41         if(y!=fa)
 42         {
 43             get1(y,x);
 44             size[x]+=size[y];
 45             wt[x]=max(wt[x],size[y]);
 46         }
 47     }
 48     wt[x]=max(wt[x],n1-size[x]);
 49     if(rt1==0||wt[x]<wt[rt1])rt1=x;
 50 }
 51 void get2(int x,int fa)
 52 {
 53     size[x]=1;
 54     wt[x]=0;
 55     for(int i=g[x];i;i=f[i].next)
 56     {
 57         int y=f[i].to;
 58         if(y!=fa)
 59         {
 60             get2(y,x);
 61             size[x]+=size[y];
 62             wt[x]=max(wt[x],size[y]);
 63         }
 64     }
 65     wt[x]=max(wt[x],n2-size[x]);
 66     if(rt2==0||wt[x]<wt[rt2])rt2=x;
 67 }
 68 void dfs(int x)
 69 {
 70     size[x]=1;
 71     for(int i=wd[x];i;i=w[i].next)
 72     {
 73         int y=w[i].to;
 74         if(fa[x]!=y)
 75         {
 76             fa[y]=x;
 77             dfs(y);
 78             size[x]+=size[y];
 79             down[x]+=down[y]+size[y];
 80         }
 81     }
 82 }
 83 void bfs(int x)
 84 {
 85     int head=0,tail=1;c[1]=1;
 86     while(head<tail)
 87     {
 88         int x=c[++head];
 89         if(x==1)up[x]=0;
 90         else up[x]=up[fa[x]]+size[1]-size[x]+down[fa[x]]-down[x]-size[x];
 91         for(int i=wd[x];i;i=w[i].next)
 92         {
 93             int y=w[i].to;
 94             if(fa[x]!=y)
 95             {
 96                 c[++tail]=y;
 97             }
 98         }
 99     }
100 }
101 int main()
102 {
103     freopen("unite.in","r",stdin);
104     freopen("unite.out","w",stdout);
105     scanf("%d%d",&n1,&n2);
106     for(int i=1,x,y;i<n1;i++)
107     {
108         scanf("%d%d",&x1[i],&y1[i]);
109         add(x1[i],y1[i]);
110         add(y1[i],x1[i]);
111     }
112     for(int i=1,x,y;i<n2;i++)
113     {
114         scanf("%d%d",&x2[i],&y2[i]);
115         odd(x2[i],y2[i]);
116         odd(y2[i],x2[i]);
117     }
118     get1(1,0);
119     get2(1,0);
120     for(int i=1,x,y;i<n1;i++)
121     {
122         add_edge(x1[i],y1[i]);
123         add_edge(y1[i],x1[i]);
124     }
125     for(int i=1,x,y;i<n2;i++)
126     {
127         add_edge(x2[i]+n1,y2[i]+n1);
128         add_edge(y2[i]+n1,x2[i]+n1);
129     }
130     add_edge(rt1,rt2+n1);
131     m=n1+n2;
132     dfs(1);    
133     bfs(1);
134     for(int i=1;i<=m;i++)
135     {
136         ans+=up[i]+down[i];
137     }
138     printf("%lld
",ans/2);
139     fclose(stdin);fclose(stdout);
140 }

【NOIP2015模拟11.4】统一天下