Submission #1517668

---

Source Code Expand

#include <iostream>
#include <vector>
#define INF 1e+9
using namespace std;

int n,k,l[100000],r[100000],num[100000];
vector<int> G[100000];
bool flag = true;

void dfs(int v,int par){
	int mi = -INF,ma = INF;
	for(int to : G[v]){
		if(to == par) continue;
		dfs(to,v);
		mi = max(mi,l[to]);
		ma = min(ma,r[to]);
	}
	if(mi == -INF) return;
	mi--;ma++;
	if(l[v] != -INF){
		if(r[v] < mi || ma < l[v]) flag = false;
	}
	else{
		if(mi > ma) flag = false;
		l[v] = mi;
		r[v] = ma;
	}
}

void solve(int v,int par){
	if(par == -1){
		if(l[v] == -INF) num[v] = 0;
		else num[v] = l[v];
	}else{
		if(l[v] <= num[par] + 1 && num[par] + 1 <= r[v]) num[v] = num[par] + 1;
		else num[v] = num[par] - 1;
	}
	for(int to : G[v]) if(to != par) solve(to,v);
}

int main(){
	cin >> n;
	for(int i = 0;i < n;i++){
		l[i] = -INF;
		r[i] = INF;
		num[i] = INF;
	}
	for(int i = 0;i < n - 1;i++){
		int a,b;
		cin >> a >> b; a--;b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	cin >> k;
	for(int i = 0;i < k;i++){
		int v,p;
		cin >> v >> p; v--;
		l[v] = p;
		r[v] = p;
	}
	dfs(0,-1);
	if(!flag){
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	solve(0,-1);
	for(int i = 0;i < n;i++) cout << num[i] << endl;
	return 0;
}

Submission Info

Judge Result