Submission #3492683

---

Source Code Expand

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define pb push_back

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
    int x(0), sgn(1); char ch(getchar());
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
    return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("E.in", "r", stdin);
	freopen ("E.out", "w", stdout);
#endif
}

const int N = 1e5 + 1e3, inf = 0x3f3f3f3f;

vector<int> G[N];

int root, n, l[N], r[N], val[N];

void Dfs(int u, int fa, int odd) {
	if (~val[u]) {
		if ((val[u] & 1) != odd) {
			puts("No"); exit(0);
		}
		l[u] = r[u] = val[u];
	} else l[u] = -1e6, r[u] = 1e6;

	for (int v : G[u]) if (v != fa) {
		Dfs(v, u, odd ^ 1);
		chkmax(l[u], l[v] - 1);
		chkmin(r[u], r[v] + 1);
	}
	if (l[u] > r[u]) {
		puts("No"); exit(0);
	}
}

int ans[N];
void Get_Ans(int u, int fa) {
	for (int v : G[u]) if (v != fa) {
		ans[v] = ans[u] + 1;
		if (ans[v] > r[v])
			ans[v] = ans[u] - 1;
		Get_Ans(v, u);
	}
}

int main () {

	File();

	Set(val, -1);

	n = read();
	For (i, 1, n - 1) {
		int u = read(), v = read();
		G[u].pb(v); G[v].pb(u);
	}

	int root = 0, k = read();
	For (i, 1, k) {
		root = read();
		val[root] = read();
	}
	Dfs(root, 0, val[root] & 1);

	puts("Yes");
	ans[root] = val[root];
	Get_Ans(root, 0);
	For (i, 1, n)
		printf ("%d\n", ans[i]);

	return 0;

}

Submission Info

Judge Result