题目链接:https://codeforc.es/contest/1388/problem/C

Problem tags
dfs and similar, dp, greedy, math, trees, *1800

题意

~~原题面是真的长,我还以为是英文阅读理解~~

给你一个根节点为1的树,总共有m个人,白天他们都在根节点工作,晚上所有人都要走最短路回到各自的家。已知家在 i 点的人数为a[i]。每个人最开始在根节点有好心情或坏心情,但是在回家的路上(经过边)好心情可能变成坏心情,一旦是坏心情,就再也不会变好了。每个点都有一个好心情探测器,它用h[i]表示所有经过 i 点的好心情人数减去坏心情人数。
你需要判断,是否存在可能,使得好心情探测器的h[i]是正确的?

思路

设sum[i]表示经过i点的总人数,good[i]表示经过i点是好心情的人数,bad[i]表示经过i点是坏心情的人数。
那么有:sum[i]=good[i]+bad[i], h[i]=good[i]-bad[i]。
消去bad[i]得到:good[i]=(sum[i]+h[i])/2
其中,h[i]已知,sum[i]实际上就是家在 i 的子树节点(包括i)的人数,在dfs回溯的时候即可求出。那么good[i]也可求出了。

然后,考虑good[i]的限制条件:
1. good[i]必须为整数,那么 sum[i]+h[i] 为偶数。
2. 0<=good[i]<=sum[i]。
3. good[v1]+good[v2]+...+good[vk]<=good[i],其中v1,v2,...,vk为 i 的子树节点(不包括i)。因为从 i 点往下走其子树节点的过程中,好心情的总人数会降低或者不变,所以经过 i 的子树节点的好心情总人数小于等于经过 i 的好心情人数。

只要满足上述三条限制条件则存在可能性。

(英语比较好的同学可以看看题解的原文)
在这里插入图片描述

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>g[N];
int a[N],h[N],sum[N],good[N],flag;
void dfs(int u,int fa)
{
    sum[u]=a[u];
    int s=0; // 记录u的所有子树节点的good人数之和
    for(int v:g[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        sum[u]+=sum[v];
        s+=good[v];
    }
    int tmp=h[u]+sum[u];
    if(tmp&1){flag=1;return;}
    good[u]=tmp/2;
    if(good[u]<0||good[u]>sum[u]||s>good[u]){flag=1;return;}
}
int main()
{
    ios::sync_with_stdio(false);
    int T,n,m,x,y;
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
        {
            cin>>h[i];
            g[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            g[x].push_back(y);
            g[y].push_back(x);
        }
        flag=0;
        dfs(1,0);
        if(flag)printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}
/*
100
5 7
0 2 2 2 1
7 2 5 2 -1
1 2
1 3
3 5
1 4
ans:NO
*/