题目:
给出一个N个点的树,找出一个点来,以这个点为根的树时,所有点的深度之和最大
题解:
水.
没开long long炸了一下.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const ll maxn = 1000010;
ll n;
struct Egde{
ll to,next;
}G[maxn<<1];
ll head[maxn],cnt;
void add(ll u,ll v){
G[++cnt].to = v;
G[cnt].next = head[u];
head[u] = cnt;
}
ll a[maxn];
ll sum[maxn],val[maxn];
#define v G[i].to
void dfs(ll u,ll f){
sum[u] = a[u];
for(ll i = head[u];i;i=G[i].next){
if(v == f) continue;
dfs(v,u);
sum[u] += sum[v];
val[u] += val[v] + sum[v];
}
}
void dfs(ll u,ll f,ll x,ll y){
sum[u] += x;val[u] += y;
for(ll i = head[u];i;i=G[i].next){
if(v == f) continue;
dfs(v,u,sum[u]-sum[v],val[u]-(val[v]+sum[v])+(sum[u]-sum[v]));
}
}
#undef v
inline void init(){
memset(head,0,sizeof head);
cnt = 0;
}
int main(){
init();read(n);
for(ll i=1,u,v;i<n;++i){
read(u);read(v);
add(u,v);add(v,u);
}
memset(val,0,sizeof val);
for(ll i=1;i<=n;++i) a[i] = 1;
dfs(1,1);dfs(1,1,0,0);
ll ans = -1,id = -1;
for(ll i=1;i<=n;++i){
if(val[i] > ans){
ans = val[i];
id = i;
}
}
printf("%lld
",id);
return 0;
}