【Luogu3478】【POI2008】STA-Station（动态规划）

题面

题目描述

给出一个\(N(2<=N<=10^6)\)个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大

题解

考虑直接对于每个点计算一次

时间复杂度\(O(n^2)\)显然无法接受

所以，考虑只进行一次\(DFS\)在通过递推求解

如果已经知道根节点的答案的话

那么，他的儿子节点很容易的可以递推出来：

\(Ans{[son]}=Ans[father]+n-2*size[son]\)

所以可以\(O(n)\)求解

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 1200000

#define ll long long

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

struct Line

{

	int v,next;

}e[MAX<<1];

int h[MAX],cnt=1;

int n;

ll dep[MAX],sum[MAX],size[MAX];

ll ans[MAX];

inline void Add(int u,int v)

{

	e[cnt]=(Line){v,h[u]};

	h[u]=cnt++;

}

void dfs(int u,int ff)

{

	sum[u]=dep[u]=dep[ff]+1;size[u]=1;

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(v==ff)continue;

		dfs(v,u);

		size[u]+=size[v];

		sum[u]+=sum[v];

	}

}

void DFS(int u,int ff)

{

	for(int i=h[u];i;i=e[i].next)

	{

		int v=e[i].v;

		if(v==ff)continue;

		ans[v]=ans[u]+n-2*size[v];

		DFS(v,u);

	}

}

int main()

{

	n=read();

	for(int i=1;i<n;++i)

	{

		int u=read(),v=read();

		Add(u,v);Add(v,u);

	}

	dfs(1,0);

	ans[1]=sum[1];

	DFS(1,0);

	int pos=1;

	for(int i=1;i<=n;++i)

		if(ans[i]>ans[pos])pos=i;

	printf("%d\n",pos);

	return 0;

}