怀抱观古今，寝食展戏谑。这篇文章主要讲述CF 660 C. Uncle Bogdan and Country Happiness相关的知识，希望能为你提供帮助。
CF 660 C. Uncle Bogdan and Country Happiness
题目链接【CF 660 C. Uncle Bogdan and Country Happiness】C. Uncle Bogdan and Country Happiness
题目概述初始时每个人都在标号为1的城市,然后回到每个人各自的城市,选择从起点到终点的最短路径,相邻城市之间的距离一样,每个人在进入一个城市时可以改变他的心情,从Good变为Bad,但是不可以从Bad变成Good,每个人进入一个城市时他的心情会影响这个城市的幸福指数,如果是Good那么指数加一否则减一,在城市里面心情是不会改变的,现在给出一种城市幸福指数的可能性,计算有没有可能得到这种幸福指数格局?
数据规模:
[1leq t leq 10000, 1leq n leq 10^5, 0leq mleq 10^9leq p_i leq m, sum_{i=1}^{n}p_i = m-10^9 leq h_i leq 10^9 , i=1,2,3dots,n.
]
思路设经过结点v的人有a个,其中好心情的有g个,坏心情的有b个,从而可以得到:
[a = g+b, h = g-b;
]
两式相加得到(g=frac{a+h}{2}),所以((a+h)\%2=0)是第一个约束条件.
有上面的式子同事可以得到另外一个明显的约束条件(0 leq g leq a),最后由于允许路上允许从高兴变成不高兴,所以在结点v的幸福指数一定不会从结点v到终点后面路径上结点的幸福指数(g_{next})之和低的.从而得到上面这三个约束条件.
这里面的主要的问题就是计算每个结点的a和g,这些有两部分组成,一部分是它自身的(p)和(frac{a+h}{2}),另外一部分是经过这个结点才能得达的结点,也就是它的后继,要先计算出后继,才能得到这个结点,然后这个结点就算出的作为上一层的后继的结果,对于那些没有后继的结点,就他的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;
}
其它
推荐阅读
- 出现Error:Execution failed for task ':app:preDebugAndroidTestBuild'. 的解决办法
- 2mapper.xml将jdbcType写错为javaType
- arduino连接NB-IOT模块M5310-A教程，app实时控制
- app性能测试指标
- MvcTest出错java.lang.IllegalStateException:Failed to load ApplicationContext
- App自动化测试
- Uni-app网络请求---uni.request
- 5.Appium的pc端实现手机端页面
- 遇到APP无法抓包怎么办