Submission #972322

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef pair<int,int> pii;

const pii inf=make_pair(-1e7,1e7);
const pii fail=make_pair(1e7,-1e7);

vector<pii> range;
vector<int> edge[100000];
bool visited[100000];

pii dfs(int v){
	if(visited[v])	return inf;
	visited[v]=true;
	for(int i=0;i<edge[v].size();i++){
		int to=edge[v][i];
		pii result=dfs(edge[v][i]);
		if(result==make_pair(inf.first-1,inf.second+1))	result=inf;
		if(result==fail)	return fail;
		else if(range[v]==inf)	range[v]=result;
		else if(result==inf)	continue;
		else if(range[v].first%2!=result.first%2)	return fail;
		else if(range[v].second<result.first)	return fail;
		else if(result.second<range[v].first)	return fail;
		else{
			range[v].second=min(range[v].second,result.second);
			range[v].first=max(range[v].first,result.first);
		}
	}
	if(range[v].second<range[v].first)	return fail;
	return make_pair(range[v].first-1,range[v].second+1);
}

void decide(int v){
	if(visited[v])	return;
	visited[v]=true;
	range[v]=make_pair(range[v].first,range[v].first);
	for(int i=0;i<edge[v].size();i++){
		int to=edge[v][i];
		if(visited[to])	continue;
		range[to]=make_pair(max(range[to].first,range[v].first-1),
							min(range[to].second,range[v].second+1));
		decide(to);
	}
	return;
}
	
int main(){
	int n;	cin>>n;
	for(int i=0;i<n-1;i++){
		int a,b;	cin>>a>>b;	a--;	b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	for(int i=0;i<n;i++)	visited[i]=false;
	range=vector<pii>(n,inf);
	int k;	cin>>k;
	for(int i=0;i<k;i++){
		int v,p;	cin>>v>>p;	v--;
		range[v]=make_pair(p,p);
	}
	pii ret=dfs(0);
	if(ret==fail){
		cout<<"No"<<endl;
		return 0;
	}
	cout<<"Yes"<<endl;
	for(int i=0;i<n;i++)	visited[i]=false;
	decide(0);
	for(int i=0;i<n;i++)	cout<<range[i].first<<endl;
	return 0;
}
	

Submission Info

Judge Result