链接
https://codeforces.com/contest/1388/problem/C
题意
$n$ 个点的树形图，树根为 $1$，有 $m$ 个人开始时在树根，心情都为好，各自回家
$p_i$ 表示点 $i$是 $p_i$ 个人的家，$h_i$ 表示经过点 $i$ 的人中心情好的人与心情不好的人的差
每个人经过任意点都有可能变成心情不好，心情不好后无法改变心情
问对于 $i(1\le i\le n)$ 是否都能与$h_i$ 相等
思路
自下而上考虑
设 $a_i$ 为经过 $i$ 但 $i$ 不是家的心情好的人，$b_i$ 为经过 $i$ 但 $i$ 不是家的心情不好的人
因此对于每个点 $i$，$p_i+b_i$ 个人心情可好可不好，假设他们心情都不好
那么对于 $a_i+x-(p_i+b_i-x)=h_i$，如果 $h_i+p_i+b_i-a_i$ 为奇数，则无解，否则算出 $x$，$a_i+x$ 为所有经过点 $i$ 的心情好的人，$p_i+b_i-x$ 为所有经过点 $i$ 的心情不好的人，判断是不是都为正即可
代码
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
| #include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,a[N],h[N],p[N];
vector<int> G[N];
bool dfs(int u,int fa) {
for(auto v:G[u]) {
if(v==fa) continue;
if(dfs(v,u)==false) return false;
a[u]+=a[v],p[u]+=p[v];
}
if((p[u]+h[u]-a[u])&1) return false;
int x=(h[u]+p[u]-a[u])/2;
if(x<0||p[u]-x<0) return false;
a[u]+=x,p[u]-=x;
return true;
}
int main() {
int T;
scanf("%d",&T);
while(T--) {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
for(int i=1;i<=n;i++) scanf("%d",&h[i]);
for(int i=1;i<=n;i++) G[i].clear(),a[i]=0;
for(int i=1;i<n;i++) {
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
if(dfs(1,0)) puts("YES");
else puts("NO");
}
return 0;
}
|