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

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

题目大意

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

solution

先考虑确定了根的情况

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

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

则以$i$为根的子树在以$fa[i]$为根的子树中贡献为$sz[i]\ast (sz[fa[i]]-sz[i])$

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

考虑换根DP

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

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

$rt$为新节点，需要向上连边，$ans+=sz[x]-1$

则总变化为$ans=ans-n+2\ast sz[x]$

求最小$ans$即可

tips

• N较大，需要手写人工栈或$bfs$
• 记得开$longlong$

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);
}

这篇关于1005.[GDOI2009五校联考] 公交网络的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---