傳送門

題意：

給你一顆$n$個點的樹，初始的時候某些點有權(quán)值$p_i$，現(xiàn)在你需要給沒給定的點賦一個權(quán)值，使得任意相鄰點權(quán)值之差的絕對值等于$1$，若無解輸出$No$。

$1\le n\le 1e5,1\le k\le n,0\le p_j\le 1e5$

思路：

考慮以定一個根，先遞歸兒子，求出兒子能取到的權(quán)值范圍，讓后根據(jù)兒子的范圍來確定當前點的范圍，不合法的話就直接輸出$No$即可。

如果合法的話，顯然從我們之前選定的根開始隨意的取一個區(qū)間內(nèi)的合法值一定可以構(gòu)造出答案。

#include<bits/stdc++.h> #define X first #define Y second #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std;const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL;int n,m; vector<int>v[N]; int a[N],col[N]; int l[N],r[N];void dfs_col(int u,int fa,int c) {col[u]=c;for(auto x:v[u]) {if(x==fa) continue;dfs_col(x,u,!c);} }void dfs(int u,int fa) {for(auto x:v[u]) {if(x==fa) continue;dfs(x,u);l[u]=max(l[u],l[x]-1);r[u]=min(r[u],r[x]+1);}if(l[u]>r[u]) {puts("No");exit(0);} }void dfs_ans(int u,int fa,int val) {a[u]=val;for(auto x:v[u]) {if(x==fa) continue;if(val-1>=l[x]&&val-1<=r[x]) dfs_ans(x,u,val-1);else dfs_ans(x,u,val+1);} }void solve() {scanf("%d",&n);for(int i=1;i<=n-1;i++) {int a,b; scanf("%d%d",&a,&b);v[a].push_back(b);v[b].push_back(a);}for(int i=1;i<=n;i++) l[i]=-INF,r[i]=INF;memset(a,-1,sizeof(a));scanf("%d",&m);for(int i=1;i<=m;i++) {int aa,b; scanf("%d%d",&aa,&b);a[aa]=b;l[aa]=b; r[aa]=b;}for(int i=1;i<=n;i++) if(a[i]>=0) {dfs_col(i,0,a[i]%2);break;}for(int i=1;i<=n;i++) if(a[i]>=0&&(a[i]%2!=col[i])) {puts("No");return;}dfs(1,0);dfs_ans(1,0,l[1]);puts("Yes");for(int i=1;i<=n;i++) printf("%d\n",a[i]);puts(""); }int main() {int _=1;while(_--) {solve();}return 0; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder Regular Contest 063 E - Integers on a Tree 构造 + 二分图染色的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。