历览千载书,时时见遗烈。这篇文章主要讲述C. Uncle Bogdan and Country Happiness solution相关的知识,希望能为你提供帮助。
C. Uncle Bogdan and Country Happinesstime limit per test
2 secondsmemory limit per test
256 megabytesinput
standard inputoutput
standard outputUncle Bogdan is in captain Flint‘s crew for a long time and sometimes gets nostalgic for his homeland. Today he told you how his country introduced a happiness index.
There are
nn
cities and
n−
1n−
1
undirected roads connecting pairs of cities. Citizens of any city can reach any other city traveling by these roads. Cities are numbered from
11
to
nn
and the city
11
is a capital. In other words, the country has a tree structure.
There are
mm
citizens living in the country. A
pipi
people live in the
ii-th city but all of them are working in the capital. At evening all citizens return to their home cities using the shortest paths.
Every person has its own mood: somebody leaves his workplace in good mood but somebody are already in bad mood. Moreover any person can ruin his mood on the way to the hometown.
If person is in bad mood he won‘t improve it.
Happiness detectors are installed in each city to monitor the happiness of
each
person who visits the city. The detector in the
ii-th city calculates a happiness index
hihi
as the number of people in good mood minus the number of people in bad mood. Let‘s say for the simplicity that
mood of a person doesn‘t change inside the city.
Happiness detector is still in development, so there is a probability of a mistake in judging a person‘s happiness. One late evening, when all citizens successfully returned home, the government asked uncle Bogdan (the best programmer of the country) to check the correctness of the collected happiness indexes.
【C. Uncle Bogdan and Country Happiness solution】Uncle Bogdan successfully solved the problem. Can you do the same?
More formally,
You need to check: "Is it possible that, after all people return home, for each city
ii
the happiness index will be equal exactly to
hihi".
InputThe first line contains a single integer
tt
(1≤
t≤
100001≤
t≤
10000)
—
the number of test cases.
The first line of each test case contains two integers
nn
and
mm
(1≤
n≤
1051≤
n≤
105;
0≤
m≤
1090≤
m≤
109)
—
the number of cities and citizens.
The second line of each test case contains
nn
integers
p1,p2,…
,pnp1,p2,…
,pn
(0≤
pi≤
m0≤
pi≤
m;
p1+p2+…
+pn=mp1+p2+…
+pn=m), where
pipi
is the number of people living in the
ii-th city.
The third line contains
nn
integers
h1,h2,…
,hnh1,h2,…
,hn
(−
109≤
hi≤
109−
109≤
hi≤
109), where
hihi
is the calculated happiness index of the
ii-th city.
Next
n−
1n−
1
lines contain description of the roads, one per line. Each line contains two integers
xixi
and
yiyi
(1≤
xi,yi≤
n1≤
xi,yi≤
n;
xi≠
yixi≠
yi), where
xixi
and
yiyi
are cities connected by the
ii-th road.
It‘s guaranteed that the sum of
nn
from all test cases doesn‘t exceed
2⋅
1052⋅
105.
OutputFor each test case, print
YES, if the collected data is correct, or
NO
—
otherwise. You can print characters in
YES
or
NO
in any case.
Examplesinput
Copy
2 7 4 1 0 1 1 0 1 0 4 0 0 -1 0 -1 0 1 2 1 3 1 4 3 5 3 6 3 7 5 11 1 2 5 2 1 -11 -2 -6 -2 -1 1 2 1 3 1 4 3 5
output Copy
YES YES
input Copy
2 4 4 1 1 1 1 4 1 -3 -1 1 2 1 3 1 4 3 13 3 3 7 13 1 4 1 2 1 3
output Copy
NO NO
solution:
#include< iostream> #include< vector> using namespace std; 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,to,i; for(i=0; i< buf[v].size(); i++){ to=buf[v][i]; if(to == ancestor) continue; dfs(to, v); a[v] += a[to]; sum += g[to]; //统计now节点为根的子树的总人数 } g[v] = (a[v]+h[v])/2; if((a[v]+h[v])%2 != 0||g[v] < 0 || g[v] > a[v]||sum > g[v]) flag = false; /*1.说明不是整数 2.说明快乐人数比总人数还多 3.说明经过now城市后的快乐人数竟然比走的更远的城市的快乐人数更少*/ } int main(int argc, const char** argv) { ios::sync_with_stdio(false); cin.tie(); 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; }
推荐阅读
- Azure Application Gateway对后端 Web App 进行负载均衡
- SpringBoot02--将application.yaml配置文件中的属性和组件中的属性进行绑定
- uni-app 功能实现
- android 字符串拼接获取图片
- ant-design-vue 之form表单中label-col和wrapper-col使用
- 安卓四大组件之服务服务的生命周期和启动方式
- Android Studio 常用快捷键(超实用!!!)
- 使用hbuilder X打包vue app
- mybatis批量添加,更新,删除(mapper.xml)