arc063e

题意：一棵n个点的树，其中一些点已经有值，需要给所有没有值的点赋值，使任意相邻的两个点相差恰好为1，求是否可行，可行求一组解。

对所有有值的点建一棵虚树，每个儿子会对父亲的取值范围和奇偶性有一个限制，从下往上dp，如果出现不合法的情况无解。之后虚树上没有值的点会有一个取值范围。从上往下dp，虚树上每个点取范围内任意一个满足奇偶性的值，并对虚树边上的点赋值，最后对不在虚树边上的点赋值。

#include <bits/stdc++.h>
using namespace std;
#define N 110000
const int inf=1e9;
int n,tot,m,cnt,top;
int head[N],nex[N<<1],to[N<<1];
int fa[N][21],deep[N];
int val[N],L[N],R[N],pos[N],a[N],st[N],sig[N];
vector<int>vec[N];
void quit(){puts("No");exit(0);}
void add(int x,int y)
{
    tot++;
    nex[tot]=head[x];head[x]=tot;
    to[tot]=y;
}
void dfs(int x,int y)
{
    fa[x][0]=y;
    for(int i=1;i<=20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    deep[x]=deep[y]+1;
    pos[x]=++cnt;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)
            dfs(to[i],x);
}
int cmp(int x,int y){return pos[x]<pos[y];}
int lca(int x,int y)
{
    if(deep[x]<deep[y])swap(x,y);
    for(int i=20;i>=0;i--)
        if(deep[fa[x][i]]>=deep[y])x=fa[x][i];
    if(x==y)return x;
    for(int i=20;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
void dfs1(int x)
{
    L[x]=-inf;R[x]=inf;sig[x]=-1;
    for(int i=0,t,d,v;i<vec[x].size();i++)
    {
        dfs1(t=vec[x][i]);
        d=deep[t]-deep[x];
        v=(R[t]+d)&1;
        L[x]=max(L[x],L[t]-d);
        R[x]=min(R[x],R[t]+d);
        if(sig[x]==-1)sig[x]=v;
        else if(sig[x]!=v)quit();
    }
    if(L[x]>R[x])quit();
    if(val[x]!=val[0])
    {
        if(val[x]<L[x]||val[x]>R[x])quit();
        if(sig[x]!=-1&&(val[x]&1)!=sig[x])quit();
        L[x]=R[x]=val[x];
    }
}
void dfs2(int x)
{
    for(int i=0,t,d,d1;i<vec[x].size();i++)
    {
        t=vec[x][i];
        d=deep[t]-deep[x];
        val[t]=max(L[t],val[x]-d);
        d1=(val[x]+d-val[t])/2;
        int now=val[t],p=t;
        for(int j=1;j<=d1;j++)
            val[fa[p][0]]=val[p]+1,p=fa[p][0];
        for(int j=1;j<d-d1;j++)
            val[fa[p][0]]=val[p]-1,p=fa[p][0];
        dfs2(t);
    }
}
void dfs3(int x,int y)
{
    if(val[x]==val[0])
        val[x]=val[y]+1;
    for(int i=head[x];i;i=nex[i])
        if(to[i]!=y)dfs3(to[i],x);
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    memset(val,-0x3f,sizeof(val));
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        scanf("%d",&val[a[i]]);
    }
    dfs(1,0);
    sort(a+1,a+1+m,cmp);
    st[top=1]=1;
    for(int i=1,t;i<=m;i++)
    {
        while((t=lca(a[i],st[top]))!=st[top])
        {
            if(deep[t]>deep[st[top-1]])
            {
                vec[t].push_back(st[top]);
                st[top]=t;
            }
            else
            {
                vec[st[top-1]].push_back(st[top]);
                top--;
            }
        }
        if(st[top]!=a[i])
            st[++top]=a[i];
    }
    for(int i=top;i>1;i--)
        vec[st[i-1]].push_back(st[i]);
    dfs1(1);
    val[1]=L[1];
    dfs2(1);
    dfs3(1,0);
    puts("Yes");
    for(int i=1;i<=n;i++)
        printf("%d\n",val[i]);
    return 0;
}