CodeForces 1388C Uncle Bogdan and Country Happiness

题意

给一棵\(n\)节点的树，每个节点有\(a[i]\)个人住，他们从\(1\)号节点回家，回家路上可能从开心的状态变成不开心的状态（但不可以由不开心变为开心），每个节点有个探测器，会探测经过该节点开心的人数减不开心的人数，而预期值为\(h[i]\)，问是否可能存在一种情况，使得所有节点的探测值等于真实值

分析

先想一下思路：我们可以发现叶子节点的人数开心人数和不开心人数，开心人数一定是从\(1\)号节点一直开心走回家的，不开心的人可能在路中间是开心的，那么我们不妨将题目转换为每个人从家出发到\(1\)号节点，他可能一开始是不开心的，他可以从不开心变为开心，但不会从开心变为不开心，那么对于一个节点，统计它的儿子节点的开心人数和不开心人数，然后不妨设该节点的所有人都是不开心，设\(x\)为开心的人数，\(y\)为不开心的人数，\(tot\)为经过该节点的总人数那么有方程

然后判断即可

#pragma GCC optimize(3, "Ofast", "inline")
 
#include <bits/stdc++.h>
 
#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define repd(z, x, y) for(int z=x;z>=y;--z)
#define com bool operator<(const node &b)const
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;
vector<int> v[maxn];
int a[maxn];
int h[maxn];
bool flag;
 
pii dfs(int now, int pre) {
    if (!flag)
        return {0, 0};
    pii p = {0, a[now]};
    for (auto &to:v[now]) {
        if (to == pre)
            continue;
        pii tmp = dfs(to, now);
        p.first += tmp.first;
        p.second += tmp.second;
    }
    int x = p.first + p.second + h[now];
    if (x & 1) {
        flag = false;
        return {0, 0};
    }
    x /= 2;
    if (x < p.first || x > p.first + p.second) {
        flag = false;
        return {0, 0};
    }
    return pii{x, p.first + p.second - x};
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    rep(i, 1, n) {
        cin >> a[i];
        v[i].clear();
    }
    rep(i, 1, n)cin >> h[i];
    rep(i, 1, n - 1) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    flag = true;
    dfs(1, 0);
    if (flag)
        cout << "YES\n";
    else
        cout << "NO\n";
}
 
signed main() {
    start;
    cin >> T;
    while (T--)
        solve();
    return 0;
}

CodeForces 1388C Uncle Bogdan and Country Happiness

原文：https://www.cnblogs.com/F-Mu/p/13412874.html