CF 660 C. Uncle Bogdan and Country Happiness

水深无声 2023-03-04 03:23 3阅读 0赞

# CF 660 C. Uncle Bogdan and Country Happiness #

## 题目链接 ##

[C. Uncle Bogdan and Country Happiness][]

## 题目概述 ##

初始时每个人都在标号为`1`的城市,然后回到每个人各自的城市,选择从起点到终点的最短路径,相邻城市之间的距离一样,每个人在进入一个城市时可以改变他的心情,从`Good`变为`Bad`,但是不可以从`Bad`变成`Good`,每个人进入一个城市时他的心情会影响这个城市的幸福指数,如果是`Good`那么指数加一否则减一,在城市里面心情是不会改变的,现在给出一种城市幸福指数的可能性,计算有没有可能得到这种幸福指数格局?

数据规模:  
 1 ≤ t ≤ 10000 , 1 ≤ n ≤ 1 0 5 , 0 ≤ m ≤ 1 0 9 0 ≤ p i ≤ m , ∑ i = 1 n p i = m − 1 0 9 ≤ h i ≤ 1 0 9 , i = 1 , 2 , 3 … , n . 1\\leq t \\leq 10000, 1\\leq n \\leq 10^5, 0\\leq m\\leq 10^9\\\\ 0\\leq p\_i \\leq m, \\sum\_\{i=1\}^\{n\}p\_i = m\\\\ -10^9 \\leq h\_i \\leq 10^9 , i=1,2,3\\dots,n. 1≤t≤10000,1≤n≤105,0≤m≤1090≤pi≤m,i=1∑npi=m−109≤hi≤109,i=1,2,3…,n.

## 思路 ##

设经过结点`v`的人有`a`个,其中好心情的有`g`个,坏心情的有`b`个,从而可以得到:  
 a = g + b , h = g − b ; a = g+b, h = g-b; a=g\+b,h=g−b;  
两式相加得到 g = a + h 2 g=\\frac\{a+h\}\{2\} g=2a\+h,所以 ( a + h ) % 2 = 0 (a+h)\\%2=0 (a\+h)%2=0是第一个约束条件.  
有上面的式子同事可以得到另外一个明显的约束条件 0 ≤ g ≤ a 0 \\leq g \\leq a 0≤g≤a,最后由于允许路上允许从高兴变成不高兴,所以在结点`v`的幸福指数一定不会从结点`v`到终点后面路径上结点的幸福指数 g n e x t g\_\{next\} gnext之和低的.从而得到上面这三个约束条件.

这里面的主要的问题就是计算每个结点的`a`和`g`,这些有两部分组成,一部分是它自身的 p p p和 a + h 2 \\frac\{a+h\}\{2\} 2a\+h,另外一部分是经过这个结点才能得达的结点,也就是它的后继,要先计算出后继,才能得到这个结点,然后这个结点就算出的作为上一层的后继的结果,对于那些没有后继的结点,就他的`a`和`g`仅由前面那一部分组成,计算后直接返回.最终的计算过程是自顶向下分解,然后求解出不可分解的部分后返回到上一层,处理上一层,然后继续返回,可以用递归方便的模拟这个过程,携程程序就是一个简单的`dfs`.

## 代码 ##

/*
     * @Author: Shuo Yang
     * @Date: 2020-07-30 21:47:50
     * @LastEditors: Shuo Yang
     * @LastEditTime: 2020-07-31 22:16:58
     * @FilePath: /Code/CF/660/C.cpp
     */ 
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1e5+5;
    vector<int>buf[N];
    int a[N],p[N],h[N],g[N];
    bool flag = true;
    
    void dfs(int v, int ancestor = -1) {
        
        a[v] = p[v];
        int sum = 0;
        for(auto to: buf[v]){
        
            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 argc, const char** argv) {
        
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int t;
        cin>>t;
        while(t--){
        
            int n,m;
            cin>>n>>m;
            for(int i = 1; i <= n; ++i)
                cin>>p[i];
            for(int i = 1; i <= n; ++i)
                cin>>h[i];
            for(int i = 0; i < n-1; ++i){
        
                int a,b;
                cin>>a>>b;
                buf[a].push_back(b);
                buf[b].push_back(a);
            }
            dfs(1);
            if( flag )
                cout<<"YES"<<endl;
            else
                cout<<"NO"<<endl;
            flag = true;
            for(int i = 1; i <=n; ++i)
                buf[i].clear();
        }
        return 0;
    }

## 其它 ##

[C. Uncle Bogdan and Country Happiness]: https://codeforces.com/contest/1388/problem/C