CF1388C Uncle Bogdan and Country Happiness 题解

题目链接：CF1388C Uncle Bogdan and Country Happiness

题意：

给出一颗根节点为 \(1\) 的树，对于每个节点 \(i\)，有 \(p_i\) 个人的家在节点 \(i\) 上。

一开始所有人都在根节点上，然后每个人会往家沿着最短路走。

每个人出发时有一个心情，可能是好心情也可能是坏心情，在经过一条边时，心情可能由好变坏，但是不可能由坏变好。

每个点有一个幸福检测器，最后的检测结果为：所有经过该节点的人中，好心情的人数减坏心情的人数。

现在给出 \(h_i\)，问有没有可能最后每个节点的检测结果恰好为 \(h_i\)。

输入格式：

第一行一个整数 \(t\) 表示有多少组数据。

每组数据中，第一行两个整数 \(n,m(1 \le n \le 10^5 , 0 \le m \le 10^9)\)，表示节点数和总人数。

第二行 \(n\) 个整数表示 \(p_i(0 \le p_i \le m,\sum p_i = m)\)。

第三行 \(n\) 个整数表示 \(h_i(-10^9 \le h_i \le 10^9)\)。

下面 \(n-1\) 行，每行两个整数 \(x,y\)，表示节点 \(x\) 和 \(y\) 之间存在一条边。

输出格式：

输出 \(t\) 行，每行为 YES 或 NO，YES 表示有可能最后每个节点的检测结果恰好为 \(h_i\)，NO 表示没有可能。

就很细节题。考虑哪些情况合法。

\(h_i\) 的绝对值不能超过 \(i\) 经过的总人数。
节点经过的人数一定为 \(2\) 的倍数。
节点经过的「心情不好的人数」一定不大于它『所有子节点经过的「心情不好的人数」之和』加上『在这个节点回家的人数』。

都很显然吧。实现的时候可以用个 pair<int,int> 来记录开心&不开心的人数。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define Fi first
#define Se second
#define N ((int)(1e5+15))

int n,m,ok,a[N],b[N],k[N],h[N],p[N];
vector<int> vec[N];
pii dfs(int u,int f)
{
    if(!ok) return {0,0};
    pii p = {0, a[u]};
    for(int v : vec[u]) if(v != f)
    {
        pii tmp = dfs(v,u);
        p.Fi += tmp.Fi; p.Se += tmp.Se;
    }
    int x = p.Fi + p.Se + h[u];
    if(x & 1) { ok = 0; return {0,0}; }
    x /= 2;
    if(x < p.Fi || x > p.Fi + p.Se){ ok = 0; return {0,0}; }
    return pii(x, p.Fi + p.Se - x);
}
void work()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) { cin >> a[i]; vec[i].clear(); }
    for(int i=1; i<=n; i++) cin >> h[i];
    for(int i=1,u,v; i<n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    ok = 1; dfs(1,0); cout << (ok ? "YES\n" : "NO\n");
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _Q; cin >> _Q; while(_Q--) work();
    return 0;
}