首页 > 代码库 > [BZOJ1131][POI2008]Sta
[BZOJ1131][POI2008]Sta
题目描述 Description |
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大 |
输入描述 Input Description |
给出一个数字N,代表有N个点.N<=1000000 下面N-1条边. |
输出描述 Output Description |
输出你所找到的点,如果具有多个解,请输出编号最小的那个. |
样例输入 Sample Input |
8 |
样例输出 Sample Output |
7 |
数据范围及提示 Data Size & Hint |
之前的一些废话:近日诸事不顺。
题解:跟之前某题基本没有区别,贴题解走人:http://www.cnblogs.com/FYH-SSGSS/p/7017092.html
代码:
#include<iostream> #include<cmath> #include<algorithm> #include<cstring> #include<queue> #include<cstdio> using namespace std; typedef long long LL; #define mem(a,b) memset(a,b,sizeof(a)) typedef pair<int,int> PII; inline int read() { int x=0,f=1;char c=getchar(); while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();} while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();} return x*f; } const int maxn=1000010; struct Edge { int u,v,next; Edge() {} Edge(int _1,int _2,int _3):u(_1),v(_2),next(_3) {} }e[maxn<<1]; int n,ce,a,b,first[maxn],size[maxn]; LL path[maxn],ans[maxn],ANS; void addEdge(int a,int b) { e[++ce]=Edge(a,b,first[a]);first[a]=ce; e[++ce]=Edge(b,a,first[b]);first[b]=ce; } void dfs(int now,int fa) { size[now]=1; for(int i=first[now];i!=-1;i=e[i].next) if(e[i].v!=fa) { dfs(e[i].v,now); size[now]+=size[e[i].v]; path[now]+=(path[e[i].v]+size[e[i].v]); } } void rdfs(int now,int fa) { for(int i=first[now];i!=-1;i=e[i].next) if(e[i].v!=fa)ans[e[i].v]=ans[now]+n-2*size[e[i].v],rdfs(e[i].v,now); } int main() { mem(first,-1); n=read(); for(int i=1;i<n;i++)a=read(),b=read(),addEdge(a,b); dfs(1,0);ans[1]=path[1];rdfs(1,0); for(int i=1;i<=n;i++)ANS=max(ANS,ans[i]); for(int i=1;i<=n;i++)if(ANS==ans[i]){printf("%d\n",i);break;} return 0; }
总结:
[BZOJ1131][POI2008]Sta
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。