首页 > 代码库 > bzoj1776[Usaco2010 Hol]cowpol 奶牛政坛*
bzoj1776[Usaco2010 Hol]cowpol 奶牛政坛*
bzoj1776[Usaco2010 Hol]cowpol 奶牛政坛
题意:
给出一个树,每个节点k个政党中的一个。问每个政党间最远的两个节点距离多少。节点数≤200000。
题解:
有个结论:每个政党所求两个节点其中一个必然是这个政党中深度最大的节点。因此枚举每个节点,计算该节点与节点所属政党深度最大节点的距离(倍增法),与给政党的答案比较即可。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 200010 7 using namespace std; 8 9 inline int read(){ 10 char ch=getchar(); int f=1,x=0; 11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} 12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); 13 return f*x; 14 } 15 struct e{int t,n;}es[maxn*2]; int g[maxn],ess; 16 void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess;} 17 int n,k,dep[maxn],d[maxn],ans[maxn],type[maxn],f[21][maxn],l; 18 void dfs(int x){ 19 for(int i=g[x];i;i=es[i].n)if(es[i].t!=f[0][x])f[0][es[i].t]=x,dep[es[i].t]=dep[x]+1,dfs(es[i].t); 20 } 21 int lca(int x,int y){ 22 if(dep[x]<dep[y])swap(x,y); int t=dep[x]-dep[y]; inc(i,0,l)if(t&(1<<i))x=f[i][x]; 23 for(int i=l;i>=0;i--)if(f[i][x]!=f[i][y])x=f[i][x],y=f[i][y]; 24 if(x==y)return x;else return f[0][x]; 25 } 26 int main(){ 27 n=read(); k=read(); inc(i,1,n){type[i]=read(); int x=read(); if(x)pe(x,i),pe(i,x);} dfs(1); 28 inc(i,1,n)if(dep[d[type[i]]]<dep[i])d[type[i]]=i; 29 for(l=0;(1<<l)<=n;l++); l--; inc(i,1,l)inc(j,1,n)f[i][j]=f[i-1][f[i-1][j]]; 30 inc(i,1,n){ans[type[i]]=max(ans[type[i]],dep[i]+dep[d[type[i]]]-2*dep[lca(i,d[type[i]])]);} 31 inc(i,1,k)printf("%d\n",ans[i]); return 0; 32 }
20160927
bzoj1776[Usaco2010 Hol]cowpol 奶牛政坛*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。