link:http://arc063.contest.atcoder.jp/tasks/arc063_c

题意:

给你一颗树,有些点有初始权值

现在求一个方案(当然如果不存在方案输出No即可)(如果方案存在,输出Yes)

把所有点都赋一个权值,每条边的权值差恰好为1

(原来有权值就不能改了)

解法:

我们随便找个根

有一个性质,就是一个点的取值范围恰好是一个区间内所有的奇数/偶数

证明不太会,但是看起来是挺对的....

那么就是,每个点是不是在取值范围里面...就行了....

如果不是就No掉

如果都是,就Yes

方案的话,我们把根当成它的l值

然后dfs下去

每个如果l可以就l,不可以就r

这样就过了

证明.....不会!

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool flag;
struct edge
{
    int y;
    edge * next;
};
edge * li[100005];
edge * new_edge()
{
    static edge a[200005];
    static int top=0;
    return &a[top++];
}
void inserts(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
void insert_edge(int x,int y)
{
    inserts(x,y);
    inserts(y,x);
}
int l[100005],r[100005];
int w[100005];
bool vis[100005];
void dfs(int x)
{
    vis[x]=true;
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (vis[t->y]) continue;
        dfs(t->y);
        l[x]=max(l[x],l[t->y]-1);
        r[x]=min(r[x],r[t->y]+1);
    }
    if (l[x]>r[x])
    {
        flag=true;
    }
    if (w[x]==-1) return;
    if (l[x]%2!=w[x]%2)
    {
        if (l[x]>-1000000) flag=true;
    }
    if (l[x]>w[x])
    {
        flag=true;
    }
    if (w[x]>r[x])
    {
        flag=true;
    }
    l[x]=w[x];
    r[x]=w[x];
}
void dfs2(int x,int val)
{
    if (w[x]==-1)
    {
        w[x]=val;
    }
    vis[x]=false;
    edge * t;
    for (t=li[x];t!=0;t=t->next)
    {
        if (vis[t->y])
        {
            int temp=val;
            if (temp<l[t->y]) temp++; else temp--;
            dfs2(t->y,temp);;
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    int i;
    for (i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        y--;
        insert_edge(x,y);
    }
    int q;
    scanf("%d",&q);
    for (i=0;i<n;i++)
    {
        l[i]=-10000000;
        r[i]=200000000;
        vis[i]=false;
        w[i]=-1;
    }
    for (i=0;i<q;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        x--;
        w[x]=y;
    }
    flag=false;
    dfs(0);
    if (flag)
    {
        puts("No");
        return 0;
    }
    puts("Yes");
    dfs2(0,l[0]);
    for (i=0;i<n;i++)
    {
        printf("%d\n",w[i]);
    }
    return 0;
}