Codeforces Round #660 (Div. 2) C - Uncle Bogdan and Country Happiness

标题:全部でn n n都市、m m mサラリーマン.都市間の連絡図は木です.各都市の総人数p i p_を与えるi piと幸福指数h i h_i hi、すべての人はすべて首都の1 1 1日(号)の1时に出勤して、すべての人の退勤する时の気持ちも异なって、退勤して家に帰る道で、すべての人はすべて家に帰る道のいかなる1つの场所の时、気持ちは楽しくて楽しくありませんから楽しくありませんて、しかし楽しくありませんから楽しくありません.都市ごとの幸福指数が与えられたh i h_と一致するような状況があるかどうかを聞く.i hiは同じです.ここでh i h_i hiは、退勤途中でその時間を通ったときの楽しい人数から、退勤途中でその時間を通ったときの不快な人数を減算することに等しい.データ範囲:1≦n≦1 0 5,0≦m≦1 0 9,Σi=1 np i=m,−1 0 9≦h i≦1 0 9 1leq nleq 10^5,0leq mleq 10^9,overset{n}{underset{i=1}{sum}}p_i=m,-10^9\leq h_i\leq 10^9 1≤n≤105,0≤m≤109,i=1∑​n​pi​=m,−109≤hi​≤109
标题:各都市について、通勤途中にその都市を通る人数をs i z[u]siz[u]siz[u]とし、その中で楽しい人数をg o o d[u]good[u]good[u]とし、楽しくない人数をb a d[u]bad[u]bad[u]とする

g o o d[u]good[u]good[u]は整数、b a d[u]bad[u]bad[u]は整数

g o o d [ u ] ≥ 0 , b a d [ u ] ≥ 0 good[u]\geq0,bad[u]\geq0 good[u]≥0,bad[u]≥0

∑ g o o d [ u s o n ] ≤ g o o d [ u ]\sum good[uson]\leq good[u] ∑good[uson]≤good[u]

コード:

#include
using namespace std;

typedef long long ll;

template<typename T>
inline T Read(){
    T s = 0, f = 1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {s = (s << 3) + (s << 1) + ch - '0'; ch = getchar();}
    return s * f;
}

#define read() Read()
#define readl() Read()

const int N = 1e5 + 10;
const int M = N << 1;

ll p[N], ha[N];
bool ans;
int h[N], e[M], ne[M], idx;
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

ll siz[N];
ll good[N];

void dfs(int u, int fa) {
	siz[u] = p[u];
	for(int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if(v == fa) continue;
		dfs(v, u);
		siz[u] += siz[v];
	} 
	good[u] = siz[u] + ha[u];
	if(good[u] & 1) ans = false; //   
	
	good[u] >>= 1;
	if(good[u] < 0 || good[u] > siz[u]) ans = false; //        
	 
	ll sgood = 0;
	for(int i = h[u]; i != -1; i = ne[i]) {
		int v = e[i];
		if(v == fa) continue;
		sgood += good[v];
	}
	if(good[u] < sgood) ans = false; //good/bad       
}

void solve() {
	idx = 0;
	int n = read(), m = read();	
	for(int i = 1; i <= n; ++i) h[i] = -1;
	for(int i = 1; i <= n; ++i) p[i] = readl();
	for(int i = 1; i <= n; ++i) ha[i] = readl();
	for(int i = 1; i < n; ++i) {
		int a = read(), b = read();
		add(a, b), add(b, a);
	}
	
	ans = true;
	dfs(1, 0);
	puts(ans ? "YES" : "NO");
}

int main()
{
	int T = read();
	for(int i = 1; i <= T; ++i) {
		solve();
	}
}