传送门
先考虑什么时候不合法。
第一是考虑任意两个特殊点的权值的奇偶性是否满足条件。
第二是考虑每个点的取值范围是否合法。
如果上述条件都满足的话就可以随便构造出一组解。
代码:
#include<bits/stdc++.h>
#define N 100005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,k,first[N],cnt,fa[N],val[N],low[N],high[N],ans[N],rt;
bool is[N];
struct edge{int v,next;}e[N<<1];
inline void add(int u,int v){e[++cnt].v=v,e[cnt].next=first[u],first[u]=cnt;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline bool dfs1(int p,int fa,bool tmp){
if(is[p]&&tmp!=(val[p]&1))return false;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
if(!dfs1(v,p,(tmp^1)))return false;
}
return true;
}
inline bool dfs2(int p,int fa){
if(is[p])low[p]=high[p]=val[p];
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
if(!dfs2(v,p))return false;
low[p]=max(low[p],low[v]-1),high[p]=min(high[p],high[v]+1);
}
return low[p]<=high[p];
}
inline void dfs3(int p,int fa,int w){
ans[p]=w;
for(int i=first[p];i;i=e[i].next){
int v=e[i].v;
if(v==fa)continue;
dfs3(v,p,(low[v]<=w-1&&high[v]>=w-1?w-1:w+1));
}
}
int main(){
n=read();
for(int i=1;i<n;++i){
int a=read(),b=read();
add(a,b),add(b,a);
}
for(int i=1;i<=n;++i)low[i]=-inf,high[i]=inf;
k=read();
for(int i=1;i<=k;++i){
int a=read(),b=read();
val[a]=b,is[a]=1,rt=a;
}
if(!dfs1(rt,0,(val[rt]&1))||!dfs2(rt,0)){puts("No");return 0;}
puts("Yes");
dfs3(rt,0,val[rt]);
for(int i=1;i<=n;++i)printf("%d\n",ans[i]);
return 0;
}