bzoj1131 [POI2008]Sta

bzoj1131 [POI2008]Sta

​​‎

Description

给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 Input

给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. Output

输出你所找到的点,如果具有多个解,请输出编号最小的那个. Sample Input 8 1 4 5 6 4 5 6 7 6 8 2 4 3 4 Sample Output 7 HINT

Source

我记得在北京八十可能讲过类似的题 其中的一部分要利用这个dp gg

大概就是首先我先dfs一下我每个子树的size然后还有他们的假的dp值 dp[i]表示以i为节点 他子树的深度是多少 经过这一次dfs 我一号节点的dp值这时候是正确的了 我再dfs2一下 做一下 子树的dp值如何做 考虑到 我从当前x->y节点我相当于经历了 我n-size[y]都增加了 并且我size[y]整体-1 那么显然我新的dp[y]=dp[x]+n-size[y]<<1;最后输出倒序扫一遍即可

#include#include#define N 1100000#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}int n,fa[N],size[N],dep[N],h[N],num;ll dp[N];struct node{ int y,next;}data[N<<1];inline void dfs(int x){ size[x]=1;dp[x]+=dep[x]; for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if (fa[x]==y) continue;fa[y]=x;dep[y]=dep[x]+1; dfs(y);size[x]+=size[y];dp[x]+=dp[y]; }}inline void dfs2(int x){ for (int i=h[x];i;i=data[i].next){ int y=data[i].y;if(fa[x]==y) continue;dp[y]=dp[x]+n-size[y]*2;dfs2(y); }}int main(){ freopen("bzoj1131.in","r",stdin); n=read(); for (int i=1;i=1;--i) if (dp[i]>=max1) max1=dp[i],id=i;printf("%d",id); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。