Submission #1517661

---

Source Code Expand

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

int n,k,l[100000],r[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 && (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 && l[v] == -INF) l[v] = l[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;
	}
	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 << l[i] << endl;
	return 0;
}

Submission Info

Judge Result