codeforces-#660-C

codeforces-#660-C

七月 31, 2020

C. Uncle Bogdan and Country Happiness

题意

有n个城市构成n-1条边的树 1号点为根

m个人每个人都在中心城市(根节点)工作

工作结束后回家 每个城市有live[i]个人居住

每个人都有mood值 1/-1当到达一个城市后他的mood值不变

但每个人可能再从某个城市到下一个城市的路中间改变他的mood值 1能变-1但是-1不能变1

现在每个城市都有happy值监测器 一个城市的happy值= 所有经过这个城市的人的mood值之和

现在给出每个城市happy预测值

问当所有人回到家后所有城市的happy值会不会出现预测值的情况

题解

我们发现一个城市i 的happy值最高不会超过以它为根的子树的城市中居住的人的总数sz[i]

最低也不会超过以它为根的子树的城市中居住的人的总数sz[i] 的相反值

同时一个城市i 的happy值-以它为根的子树的城市中居住的人的总数sz[i]应该是偶数

比如一个城市的happy值为7而sz[i]=10

假如10个人路过这里mood都为1那么 happy值为10

假如10个人中有一个mood为-1那么happy值为8

有两个mood为-1那么happy值为6

发现一个人mood由1变-1总的happy值-2 所以这个城市i的happy值 - sz[i]=偶数

因为有的人经过这个城市后mood由1变为-1 而有的人住在这个城市不会继续往后走

假设留在这个城市i的人mood都是-1那么 happy[i]>= sumhpson[i]-live[i]

假设留在这个城市i的人mood都是1那么 happy[i]>=sumhpson[i]+live[i]

sumhpson[i]表示城市i直接连接的子节点城市的happy值之和

所以显然一个城市i 的happy值应该比sumhpson[i]-live[i] 大

dfs统计sz并维护sumhpson

依靠这几个条件判断每个城市是否符合要求

还有另外一种判断方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
int live[Max],hp[Max];
vector<int>mp[Max];
int sumhpson[Max],sz[Max];
/*
*/
 
void dfs_size(int now,int f){
    for(auto i:mp[now]){
        if(i==f)continue;
        sumhpson[now]+=hp[i];
        dfs_size(i,now);
        sz[now]+=sz[i];
        //cout<<now<<" "<<i<<endl;
    }
    return;
}
 
int main() {
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        for(int i=1;i<=n;i++)mp[i].clear();
        for(int i=1;i<=n;i++){
            cin>>live[i];
            sz[i]=live[i];
            sumhpson[i]=0;
        }
        //minhpfa[0]=1e9+5;
        for(int i=1;i<=n;i++){
            cin>>hp[i];
            //minhpfa[i]=hp[i];
            //maxhpson[i]=hp[i];
            //sumhpson[i]=hp[i];
        }
        for(int i=1;i<n;i++){
            int u,v;cin>>u>>v;
            mp[u].push_back(v);
            mp[v].push_back(u);
        }
        //cout<<endl;
        dfs_size(1,0);bool flag=0;
        for(int i=1;i<=n;i++){
            //cout<<i<<" "<<hp[i]<<" "<<sumhpson[i]+sz[i]<<" "<<-sz[i]<<" "<<sz[i]<<endl;
            if((hp[i]-sz[i])%2||hp[i]<-sz[i]||hp[i]>sz[i]||sumhpson[i]-live[i]>hp[i]){
                flag=1;
                //cout<<i<<endl;
            }
        }
        if(flag)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
}