「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
1 4
5 6
4 5
6 7
6 8
2 4
3 4
Sample Output
7
题解
发现从根从某个位置移到它的一个子树得出ans只要O1的时间
那么树形dp即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll f[1000005]; int n,cnt,ans; int last[1000005],deep[1000005],size[1000005]; struct edge{int to,next;}e[2000005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dfs1(int x,int fa) { size[x]=1; f[x]=deep[x]; for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { deep[e[i].to]=deep[x]+1; dfs1(e[i].to,x); f[x]+=f[e[i].to]; size[x]+=size[e[i].to]; } } void dfs2(int x,int fa) { for(int i=last[x];i;i=e[i].next) if(e[i].to!=fa) { f[e[i].to]=f[x]+n-2*size[e[i].to]; dfs2(e[i].to,x); } } int main() { n=read(); for(int i=1;i<n;i++) { int a=read(),b=read(); insert(a,b); } dfs1(1,0); dfs2(1,0); for(int i=1;i<=n;i++) if(f[i]>f[ans])ans=i; printf("%d",ans); return 0; } |
Subscribe
计数器 9793795
OI 课件=>
OI 课件=>