1005.[GDOI2009五校联考] 公交网络

本文主要是介绍1005.[GDOI2009五校联考] 公交网络，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

给出一颗N个点的无根树，定义两点间距离为当其中一点为另一点祖先时为1，否则为2，求最短距离和

solution

先考虑确定了根的情况

设 $s z [i]$ 为以 $i$ 为根的子树大小（包括 $i$ ）

则在以 $f a [i]$ 为根的子树中，以 $i$ 为根的子树中每一个都要向外连 $s z [f a [i]] - s z [i]$ 条边

则以 $i$ 为根的子树在以 $f a [i]$ 为根的子树中贡献为 $s z [i] * (s z [f a [i]] - s z [i])$

则答案为 $\sum_{i=1}^{n}\sum_{j=son}sz[j]*(sz[i]-sz[j])$

考虑换根DP

对于当前根为 $r t$ ，要换为 $i$ 的情况，

$i$ 为新根，则无需向上连边， $a n s - = n - s z [x] - 1$

$r t$ 为新节点，需要向上连边， $a n s + = s z [x] - 1$

则总变化为 $a n s = a n s - n + 2 * s z [x]$

求最小 $a n s$ 即可

tips

N较大，需要手写人工栈或 $b f s$
记得开 $long\ long$

code

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
#define inf 1000000007
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
int n,tot,G,top,k[N];
ll mans=0x7f7f7f7f7f7f7f,ans[N],sz[N];
struct tree{int st,to,nxt;
}t[N*2];
pair<int,int> st[N];
int read(){int res=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'&&((ch=getchar())>='0'&&(ch)<='9')) f=-1;else ch=getchar();}while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();return res*f;
}
void add(int u,int v){t[++tot].nxt=t[u].st,t[tot].to=v,t[u].st=tot;
}
void Add(int u,int v){add(u,v),add(v,u);
}
void dfs(int x,int fa){st[top=1]=make_pair(x,fa);while(top){int now=st[top].first,nf=st[top].second;if(!k[now]){sz[now]=1;k[now]=t[now].st;}else sz[now]+=sz[t[k[now]].to],k[now]=t[k[now]].nxt;bool bz=1;for(int i=k[now];i;i=(k[now]=t[i].nxt)){int v=t[i].to;if(v==nf)continue;st[++top]=make_pair(v,now);bz=0;break;}if(!bz)continue;for(int i=t[now].st;i;i=t[i].nxt){int v=t[i].to;if(v==nf)continue;ans[1]+=sz[v]*(sz[now]-sz[v]-1);}ans[1]+=sz[now]-1;--top;}
}
void dp(int x,int fa){st[top=1]=make_pair(x,fa);while(top){int now=st[top].first,nf=st[top].second;if(!k[now]){if(nf)ans[now]=ans[nf]-n+2*sz[now],sz[nf]=n-sz[now],sz[now]=n;k[now]=t[now].st;}else k[now]=t[k[now]].nxt;bool bz=1;for(int i=k[now];i;i=(k[now]=t[i].nxt)){int v=t[i].to;if(v==nf)continue;st[++top]=make_pair(v,now);bz=0;break;}if(!bz)continue;if(nf)sz[now]=n-sz[nf],sz[nf]=n;--top;}
}
int main(){freopen("transport.in","r",stdin);freopen("transport.out","w",stdout);n=read();fo(i,1,n-1){int u=read(),v=read();Add(u,v);}dfs(1,0);top=0;memset(k,0,sizeof k);dp(1,0);fo(i,1,n)mans=min(mans,ans[i]);printf("%lld",mans);
}