Submission #1513484

---

Source Code Expand

#include <cmath>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
struct state { int pos, val; };
bool operator<(const state& s1, const state& s2) { return s1.val > s2.val; }
int N, K, a, b, c[100009], p[100009]; vector<int> g[100009];
int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b; a--, b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	fill(c, c + N, -1);
	fill(p, p + N, -1);
	cin >> K;
	priority_queue<state> que;
	for (int i = 0; i < K; i++) {
		cin >> a >> b, c[--a] = b;
		que.push(state{ a, b }); p[a] = b;
	}
	while (!que.empty()) {
		state u = que.top(); que.pop();
		for (int i : g[u.pos]) {
			if (p[i] == -1 || p[i] > p[u.pos] + 1) {
				p[i] = p[u.pos] + 1;
				que.push(state{ i, p[i] });
			}
		}
	}
	bool f = true;
	for (int i = 0; i < N; i++) {
		if (c[i] != -1 && p[i] != c[i]) f = false;
		for (int j : g[i]) {
			if (abs(p[i] - p[j]) != 1) f = false;
		}
	}
	if (!f) cout << "No" << endl;
	else {
		cout << "Yes" << endl;
		for (int i = 0; i < N; i++) cout << p[i] << endl;
	}
	return 0;
}

Submission Info

Judge Result