[BZOJ1131] [POI2008]Sta

本文主要是介绍[BZOJ1131] [POI2008]Sta，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

http://www.lydsy.com/JudgeOnline/problem.php?id=1131

题目大意

给定一棵树,找到一个根,使所有点的深度和最大

题解

树形DP
我们先把这棵树处理成以1为根的有根树
维护以每个点为根的子树的节点数$size[]$
我们逐层$O(1)$查询
设$a=fa[b],且已知ans[a]$
$那么从a为根转为b为根,b的子树中的点深度都-1,其他点深度都+1$
所以得到递推式$ans[i]=ans[fa[i]]-size[i]+n-size[i]$

{$m 10000000}
constmaxn=1000005;
varw:array[0..3*maxn,1..2]of longint;size,fa:array[0..maxn]of longint;ans:array[0..maxn]of int64;i,j,k:longint;n,m,len,a,b,anss:longint;
procedure init(a,b:longint);
beginw[len,1]:=b;if w[a,2]=0then w[a,2]:=len else w[w[a,1],2]:=len;w[a,1]:=len; inc(len);
end;procedure dfs1(a:longint);
var tt:longint;
beginsize[a]:=1; tt:=w[a,2];while tt<>0 dobeginif w[tt,1]<>fa[a]thenbeginfa[w[tt,1]]:=a;dfs1(w[tt,1]);inc(size[a],size[w[tt,1]]);ans[a]:=ans[w[tt,1]]+size[w[tt,1]];end;tt:=w[tt,2];end;
end;procedure dfs2(a:longint);
var tt:longint;
begintt:=w[a,2];if a<>1then ans[a]:=ans[fa[a]]+n-size[a]-size[a];while tt<>0 dobeginif w[tt,1]<>fa[a]then dfs2(w[tt,1]);tt:=w[tt,2];end;
end;beginreadln(n); len:=n+1;for i:=1 to n-1 dobeginreadln(a,b);init(a,b); init(b,a);end;dfs1(1);dfs2(1);anss:=0; ans[0]:=-1;for i:=1 to n doif ans[anss]<ans[i]then anss:=i;writeln(anss);
end.

这篇关于[BZOJ1131] [POI2008]Sta的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---