搜狗网站排名怎么做,网页设计图片切换怎么做,北京软件开发平均工资,视频小广告是怎么制作的传送门
题意#xff1a;
给你一颗nnn个点的树#xff0c;初始的时候某些点有权值pip_ipi#xff0c;现在你需要给没给定的点赋一个权值#xff0c;使得任意相邻点权值之差的绝对值等于111#xff0c;若无解输出NoNoNo。 1≤n≤1e5,1≤k≤n,0≤pj≤1e51\le n\le 1e5,1\…传送门
题意
给你一颗nnn个点的树初始的时候某些点有权值pip_ipi现在你需要给没给定的点赋一个权值使得任意相邻点权值之差的绝对值等于111若无解输出NoNoNo。
1≤n≤1e5,1≤k≤n,0≤pj≤1e51\le n\le 1e5,1\le k\le n,0\le p_j\le 1e51≤n≤1e5,1≤k≤n,0≤pj≤1e5
思路
考虑以定一个根先递归儿子求出儿子能取到的权值范围让后根据儿子的范围来确定当前点的范围不合法的话就直接输出NoNoNo即可。
如果合法的话显然从我们之前选定的根开始随意的取一个区间内的合法值一定可以构造出答案。
#includebits/stdc.h
#define X first
#define Y second
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N1000010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n,m;
vectorintv[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(xfa) continue;dfs_col(x,u,!c);}
}void dfs(int u,int fa) {for(auto x:v[u]) {if(xfa) 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(xfa) continue;if(val-1l[x]val-1r[x]) dfs_ans(x,u,val-1);else dfs_ans(x,u,val1);}
}void solve() {scanf(%d,n);for(int i1;in-1;i) {int a,b; scanf(%d%d,a,b);v[a].push_back(b);v[b].push_back(a);}for(int i1;in;i) l[i]-INF,r[i]INF;memset(a,-1,sizeof(a));scanf(%d,m);for(int i1;im;i) {int aa,b; scanf(%d%d,aa,b);a[aa]b;l[aa]b; r[aa]b;}for(int i1;in;i) if(a[i]0) {dfs_col(i,0,a[i]%2);break;}for(int i1;in;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 i1;in;i) printf(%d\n,a[i]);puts();
}int main() {int _1;while(_--) {solve();}return 0;
}
