Codeforces Round #527 (Div. 3)F(DFS,DP)
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int n,A[N];
long long Mx,tot,S[N];
vector<int>Adj[N];
void DFS(int v,int p){
S[v]=A[v];
for(int &u:Adj[v])
if(u!=p)
DFS(u,v),S[v]+=S[u];
if(p)//0号结点是不存在的
tot+=S[v];
}
void DFS2(int v,int p){
Mx=max(Mx,tot);
for(int &u:Adj[v])
if(u != p){
tot-=S[u];//换根后新根子树的权重会减小一段,即减为一半
tot+=S[1]-S[u];//换根后新根子树的父结点与新根结点子树权重的差值会增大一段,即增加一倍
DFS2(u,v);//对新根继续深度优先搜索
tot-=S[1]-S[u];//还原为原值
tot+=S[u];//同上
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&A[i]);
for(int i=1,v,u;i<n;i++)
scanf("%d%d",&v,&u),Adj[v].push_back(u),Adj[u].push_back(v);
DFS(1,0);//深度优先搜索每个结点子树(包含当前结点)的权重
DFS2(1,0);//深度优先搜索换根后的WPL值
return !printf("%lld",Mx);
}
最新文章
- [Android Pro] android 混淆文件project.properties和proguard-project.txt
- javassist动态修改class
- 采用软件nginx实现web服务器集群
- BZOJ2292: 【POJ Challenge 】永远挑战
- iOS6和iOS7代码的适配(2)——status bar
- css3 3d学习心得
- apache服务器绑定泛解析域名
- Vue(小案例_vue+axios仿手机app)_购物车(二模拟淘宝购物车页面,点击加减做出相应变化)
- loadrunner使用https请求
- bzoj 4260: Codechef REBXOR (01 Trie)
- Kafka基本命令
- IntelliJ IDEA 集成 SVN
- Oracle 服务器运行健康状况监控利器 Spotlight on Oracle 的安装与使用
- 百度AI搜索引擎
- hibernate 中,出现了错误 ";node to traverse cannot be null!"; 如何改正
- 【WP8】自定义控件
- 简单的Slony-I设置实例 II
- HDU 2897 邂逅明下 (博弈)
- Java设计模式学习01——单例模式(转)
- UML学习-1 UML 简介
热门文章
- 分享知识-快乐自己:Spring整合定时器
- node.js定时任务:node-schedule的使用
- Twitter的流处理器系统Heron——升级的storm,可以利用mesos来进行资源调度
- Debian for ARM install python 3.5.x
- 打包AAC码流到FLV文件
- 点分治Day1
- BZOJ5442: [Ceoi2018]Global warming
- 【LeetCode】060. Permutation Sequence
- Python 中list, dictionary 与 file相互操作
- CentOS配置LDAP服务器