Description

一棵树,问以那个节点为根时根的总和最大.

Sol

DFS+树形DP.

第一遍统计一下 size 和 d.

第二遍转移根,统计答案就行了.

Code

/**************************************************************
Problem: 1131
User: BeiYu
Language: C++
Result: Accepted
Time:8028 ms
Memory:78700 kb
****************************************************************/ #include <cstdio>
#include <vector>
#include <iostream>
using namespace std; typedef long long LL;
const int N = 1000005; int n;
int s[N],d[N];
LL sd[N];
LL ans1,ans2;
int nxt[N<<1],gto[N<<1],e,h[N]; inline int in(int x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; } void Add_Edge(int fr,int to){ nxt[++e]=h[fr],gto[e]=to,h[fr]=e; } void DFS1(int u=1,int fa=0) {
s[u]=1,sd[u]=d[u]=d[fa]+1;
for(int i=h[u],v;i;i=nxt[i]) if((v=gto[i])!=fa) {
DFS1(v,u),s[u]+=s[v],sd[u]+=sd[v];
}
}
void DFS2(int u=1,int fa=1,LL x=0) {
LL res=x+(sd[u]-(LL)d[u]*s[u]);
// cout<<u<<" "<<res<<endl;
if(ans2<res || (ans2==res && ans1>u)) ans1=u,ans2=res;
for(int i=h[u],v;i;i=nxt[i]) if((v=gto[i])!=fa) {
DFS2(v,u,x+n-s[v]+(sd[u]-sd[v])-(LL)d[u]*(s[u]-s[v]));
}
} int main(){
// freopen("in.in","r",stdin); n=in();
for(int i=1,u,v;i<n;i++) u=in(),v=in(),Add_Edge(u,v),Add_Edge(v,u); d[0]=-1;
DFS1();
ans1=1,ans2=sd[1];
DFS2();
cout<<ans1<<endl; return 0;
}

  

最新文章

  1. jquery.nicescroll.js可全屏可改滚动条颜色的滚动条插件-推荐
  2. call和bind改变的上下文环境
  3. 文件上传之Apache commons fileupload使用
  4. [Liferay6.2.2]AUI的小坑:input的type属性
  5. hdu2546 01背包
  6. raw_input 和input的区别
  7. uva 10375
  8. MySQL预处理语句
  9. [UVA796]Critical Links(割边, 桥)
  10. 【转】匹配dll(exe)和pdb方法
  11. CentOS 6.5 + Nginx 1.8.0 + PHP 5.6(with PHP-FPM) 负载均衡源码安装 之 (二)PHP(PHP-FPM)安装篇
  12. 老李推荐: 第1章1节《MonkeyRunner源码剖析》概述:前言
  13. LINUX服务器上新增用户名
  14. 自己写的,然后配合zepto+iscroll的上拉加载
  15. L1范数与L2范数​
  16. [USACO18DEC]The Cow Gathering
  17. return ajax 把ajax链式操作 简易封装
  18. LeetCode13.罗马数字转整数
  19. CentOS 下搭建Jenkins
  20. spring 使用 maven profile

热门文章

  1. UML九种图作用简介
  2. [codevs 2800]送外卖
  3. c# 调用c++DLL方法及注意事项
  4. ros下boost移植
  5. ElasticSearch第一步-环境配置
  6. no result defined for action
  7. 网页游戏外挂辅助AMF模拟通讯必备
  8. C语言拾遗(一)
  9. deepin 15.3 安装配置nginx
  10. UEditor独立图片、文件上传模块