【AtCoder Regular Contest 063 E】Integers on a Tree | Mrsrz's blog

贪心，构造。

题目大意：

给定一棵树，有些点已经有点权了。

现在要给剩下的点标上点权，要求满足：任意两个有边相连的结点，点权之差恰好为 $1$。

问是否有可行方案。如果有输出一种。

题解：

我们用一个堆来存放已经有点权的点，按照点权排序。

每次选择已经标号的点权最小的点，设点权为 $x$，并检查与它相连的点。如果有未标点权的，则令其点权为 $x+1$。如果有已经标上点权，但是差不为 $1$ 的，则说明无解。

感性理解：由于我们每次取出当前最小的结点，说明点权小于它的结点四周已经符合条件。那么我们只需要考虑点权大于等于 $x$ 的点。若标 $x-1$ 有合法方案，则标 $x+1$ 也能达到同样效果。反之不一定。由于我们一直在往大了标号，所以若发现冲突，则一定不存在合法方案。

Code：

#include<queue>
#include<cstdio>
#include<cstdlib>
const int N=1e5+6;
using namespace std;
struct data{
    int u,d;
    inline bool operator<(const data&rhs)const{return d>rhs.d;}
};
priority_queue<data>q;
int n,k,w[N];
bool vis[N];
vector<int>G[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v),G[v].push_back(u);
    }
    scanf("%d",&k);
    if(!k)vis[1]=1,w[1]=114514,q.push((data){1,114514});
    while(k--){
        int u,v;
        scanf("%d%d",&u,&v),w[u]=v,vis[u]=1;
        q.push((data){u,v});
    }
    while(!q.empty()){
        int u=q.top().u;q.pop();
        for(int to:G[u])if(!vis[to])vis[to]=1,w[to]=w[u]+1,q.push((data){to,w[to]});else
        if(abs(w[to]-w[u])!=1)return puts("No"),0;
    }
    puts("Yes");
    for(int i=1;i<=n;++i)printf("%d\n",w[i]);
    return 0;
}