POI2008 Station

POI2008 Station

题目大意：

给出n个节点的树，找出一个点来，在以这个点为根时，所有的点的深度之和最大。

题解：

感觉是做过来最简单的一道题。

随便树形dp一下就没了。

Code：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);	
}
const int N=1000005;
int n,tot_edge,head[N];
struct Edge{
	int to,nxt;
}edge[N<<1];
void add_edge(int a,int b){
	edge[tot_edge]=(Edge){b,head[a]};
	head[a]=tot_edge++;
}
int cnt[N];
ll sum[N];
void dfs(int p,int f){
	cnt[p]=1;
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		dfs(to,p);
		cnt[p]+=cnt[to];
	}
}
void solve(int p,int f){
	for(int i=head[p];~i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		sum[to]=sum[p]+n-cnt[to]*2;
		solve(to,p);
	}
}
int main(){
	Rd(n);
	memset(head,-1,sizeof(head));
	for(int i=1,a,b;i<n;i++){
		Rd(a),Rd(b);
		add_edge(a,b);
		add_edge(b,a);		
	}
	dfs(1,0);
	solve(1,0);
	ll mx=-1;int ans_id;
	for(int i=1;i<=n;i++)
		if(sum[i]>mx)mx=sum[i],ans_id=i;
	printf("%d\n",ans_id);
	return 0;
}