题意:
有 n 个点 n-1 条边的数, 问每个点所在子树中白黑点数目最大差.
思路:
白点先由下至上汇集, 后由上至下分并.
- #include <bits/stdc++.h>
- using namespace std;
- const int M=220000;
- vector<vector<int>> e(M);
- int n,a[M];
- void dfs1(int u,int pre){
- for(int v:e[u]){
- if(v!=pre){
- dfs1(v,u);
- a[u]+=max(0,a[v]);
- }
- }
- }
- void dfs2(int u,int pre){
- for(int v:e[u]){
- if(v!=pre){
- a[v]+=max(0,a[u]-max(0,a[v]));
- dfs2(v,u);
- }
- }
- }
- int main(){
- cin>>n;
- for(int i=0;i<n;i++){
- cin>>a[i];
- if(a[i]==0) a[i]=-1;
- }
- for(int i=0;i<n-1;i++){
- int u,v;cin>>u>>v;
- --u,--v;
- e[u].push_back(v);
- e[v].push_back(u);
- }
- dfs1(0,-1);
- dfs2(0,-1);
- for(int i=0;i<n;i++) cout<<a[i]<<' ';
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3459521.html