C. Uncle Bogdan and Country Happiness(dfs + 回溯)
Problem - C - Codeforces
波格丹叔叔在弗林特船长的团队里待了很长一段时间，有时会怀念他的家乡。今天他告诉你他的国家是如何引入幸福指数的。有n个城市和n -1条连接城市的无方向道路。任何城市的公民都可以通过这些道路到达任何其他城市。城市编号从1到n，城市1是首都。换句话说，这个国家有一个树形结构。有100万公民居住在这个国家。有很多人住在第i个城市，但他们都在首都工作。傍晚时分，所有市民都选择最短路径返回各自的城市。每个人都有自己的心情:有的人带着好心情离开，有的人已经心情不好了。此外，任何人都可以破坏他的心情在回家的路上。如果一个人心情不好，他不会改善它。每个城市都安装了幸福探测器，以监测每个到访城市的人的幸福程度。第i个城市的检测器计算出幸福指数h，即心情好的人数减去心情不好的人数。简单地说，一个人的情绪在城市里是不变的幸福检测仪仍在开发中，所以判断一个人的幸福有可能会出错。一天深夜，当所有市民都顺利回家后，政府请Bogdan叔叔(全国最好的程序员)检查收集到的幸福指数是否正确。Bogdan叔叔成功地解决了这个问题。你也能做到吗?更正式地说，你需要检查:“有没有可能，在所有人都回家后，每个城市i的幸福指数都恰好等于hi”。输入第一行包含一个整数t (1 < t < 10000)——测试用例的数量。每个测试用例的第一行包含两个整数n和m (1 < n < 105;0 < m < 10°)-城市和公民的数量。每个测试用例的第二行包含n个整数p1,P2，，Pn(0≤pi < m;P1 + p2 +。+ pn = m)，其中p;是居住在第i个城市的人数。第三行包含n个整数h1, h2，， hn(-10°< h;< 10°)，其中h;计算出的幸福指数是第i个城市吗接下来的n - 1行包含道路的描述，每行一个。每行包含两个整数x;和yi (1 S xi, yi S n;和y;是由第i条公路连接的城市吗?可以保证所有测试用例的n的和不超过2 - 105。输出对于每个测试用例，如果收集的数据正确，则打印YES，否则打印NO。在任何情况下，都可以打印YES或NO中的字符。
Examples
input
Copy
2 7 4 1 0 1 1 0 1 0 4 0 0 -1 0 -1 0 1 2 1 3 1 4 3 5 3 6 3 7 5 11 1 2 5 2 1 -11 -2 -6 -2 -1 1 2 1 3 1 4 3 5
output
Copy
YES YES
input
Copy
2 4 4 1 1 1 1 4 1 -3 -1 1 2 1 3 1 4 3 13 3 3 7 13 1 4 1 2 1 3
output
Copy
NO NO
题解:
首先我们应该明白如果从根节点开始考虑的话,不确定的状态太多,不好考虑,所以应该从叶子节点考虑
对于题意来说不满足的情况有这么几种,
1.(子树城市居民数 + 城市心情值)% 2 == 1 (假设居民心情全为正的或全为负的,一个人心情变化,变化结果就是2)
2.假如说y是x的子节点,那么y的市民好心情数,肯定不能大于x(因为居民回家途中心情只可能变坏,不可能变好)
3.一个城市居民好心情数目,应该 = (子树城市居民数 + 城市心情值)/2 ,人数不能小于0
4,同理坏心情数目也不能小于0
剩下就是很完美的代码实现,非常简洁(只能说大佬的代码能力和常人确实不是一个级别)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int long long
vector<int> p[100050];
int good[100050];
int son[100050];
int h[100050];
int a[100050];
int f;
void dfs(int x,int fa)
{son[x] = a[x];int s = 0;for(auto ne:p[x]){if(ne == fa)continue;dfs(ne,x);son[x] += son[ne];s += good[ne];}good[x] = (son[x] + h[x])/2;if(abs(son[x] + h[x])%2 == 1||s > good[x] || good[x] < 0||son[x] - good[x] < 0){f = 1;}
}
void solve()
{f = 0;int n,m;cin >> n >> m;for(int i = 1;i <= n;i++){cin >> a[i];}for(int i = 1;i <= n;i++){cin >> h[i];}for(int i = 1;i < n;i++){int l,r;cin >> l >> r;p[l].push_back(r);p[r].push_back(l); } dfs(1,1);if(f){cout <<"NO\\n";}else{cout <<"YES\\n";}for(int i = 1;i <= n;i++){p[i].clear();son[i] = 0;good[i] = 0;}
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--){solve(); }
}