CF #660 C - Uncle Bogdan and Country Happiness


	CF #660 C - Uncle Bogdan and Country Happiness
[编程语言教程]

#include<iostream>
#include<vector>
using namespace std;
#define MAX 10005
#define REP(i,b,e) for(int i=b;i<e;i++)
vector<int>b[MAX];
int a[MAX], p[MAX], h[MAX], g[MAX];
bool flag = true;

void dfs(int v, int ancestor = -1) {
    a[v] = p[v];//a=总人口
    int sum = 0,to,i;
    REP(i,0,b[v].size()){
        to = b[v][i];
        if (to == ancestor)
            continue;
        dfs(to, v);
        a[v] += a[to];
        sum += g[to];
    }
    g[v] = (a[v] + h[v]) / 2;
    if ((a[v] + h[v]) % 2 != 0)//无法分配
        flag = false;
    if (g[v] < 0 || g[v] > a[v])//指数过小或过大
        flag = false;
    if (sum > g[v])//后续超出前段的
        flag = false;
}


int main() {
    int t;
    cin >> t;
    while (t--) {
        int n,m;cin>>n>>m;
        
        REP(i,0,n)
            cin >> p[i+1];
        REP(i,0,n)
            cin >> h[i+1];
        REP(i,1,n){
            int a1, b1;
            cin >> a1 >> b1;
            b[a1].push_back(b1);
            b[b1].push_back(a1);
        }
        dfs(1);
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
        flag = true;
        for (int i = 1; i <= n; ++i)
            b[i].clear();
    }
    return 0;
}

https://vjudge.net/contest/387172#problem/C

CF #660 C - Uncle Bogdan and Country Happiness

原文地址:https://www.cnblogs.com/forwhat00/p/13448781.html