[CF_#660] C. Uncle Bogdan and Country Happiness

本文主要是介绍[CF_#660] C. Uncle Bogdan and Country Happiness，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

C. Uncle Bogdan and Country Happiness

1.分析：

本题可以用树上dfs预处理数据，再check的方式求解。
限制条件：
1.每个点的坏人数量是整数。
2.每个点的坏人数量大于子节点的坏人数量和+居民。（否则无法合理更新子节点）
3.每个点坏人的数量是正数。

2.算法描述

先树上dfs预处理出每个点会经过多少人，再判断（预处理）出每个点会经过多少坏人，最后check。

3.具体代码

#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;int h[N],e[N*2],ne[2*N],idx;//建树
int hh[N],ch[N];//hh和ch分别为每个点的读入信息（hh：因为会和h数组重名，所以叫hh；ch：常住的意思）
int bad[N],liu[N];//bad存储当前节点有几个坏人，liu表示当前节点一共会经过多少人（流量）
int sum[N];//表示当前点的儿子坏人数和，叶子节点为0
int n,m;
bool flag=true;
void init()
{memset(h,-1,sizeof h);idx=0;flag=true;
}
void add(int a,int b)
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}void dfs(int u,int fa)
{liu[u]=ch[u];for(int i=h[u];~i;i=ne[i]){if(e[i]==fa)    continue;dfs(e[i],u);}for(int i=h[u];~i;i=ne[i]){if(e[i]==fa)    continue;liu[u]+=liu[e[i]];}
}void dfs1(int u,int fa)
{sum[u]=0;for(int i=h[u];~i;i=ne[i]){if(e[i]==fa)    continue;dfs1(e[i],u);}for(int i=h[u];~i;i=ne[i]){if(e[i]==fa)    continue;sum[u]+=bad[e[i]];}
}int main()
{int T ;scanf("%d",&T);while(T -- ){init();scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&ch[i]);}for(int i=1;i<=n;i++){scanf("%d",&hh[i]);}for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}dfs(1,0);//预处理出liu[]for(int i=1;i<=n;i++)//判断，并求出bad[]{if((liu[i]-hh[i])%2 == 0)   bad[i]=(liu[i]-hh[i])/2;else{flag=0;break;}}if(!flag){printf("NO\n");continue;}dfs1(1,0);//预处理出sum[]for(int i=1;i<=n;i++){if(bad[i]>ch[i]+sum[i] || bad[i]<0)flag=0;}if(flag){printf("YES\n");}elseprintf("NO\n");}return 0;
}