AtCoder Regular Contest 063 E：Integers on a Tree

题目传送门：https://arc063.contest.atcoder.jp/tasks/arc063_c

题目翻译

给你一个树，上面有\(k\)个点有权值，问你是否能把剩下的\(n-k\)个点全部填上权值，使得每条边链接的两个点权值相差\(1\)，如果可以做到需要输出任意一组方案。

题解

我们考虑每条边权值为\(1\)或\(-1\)，那么相当于黑白染色一样，所有点权值的奇偶性也都是确定的。如果与读入的\(k\)个点中某个点相冲突了就\(GG\)。另外每个点的取值范围都可以转化成一段区间\([l,r]\)内的奇/偶数，假设父亲的值域区间为\([l,r]\)，那么儿子的值域区间就可以是\([l-1,r+1]\)，同样的，值域区间也可以通过儿子转移过来。如果区间的交为空那么就无解。确定值域区间之后再自上而下确定权值即可。

时间复杂度：\(O(n)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=1e5+5;

int n,k,tot,rt;

bool fake,bo[maxn];

int now[maxn],pre[maxn*2],son[maxn*2];

int l[maxn],r[maxn],odd[maxn],ans[maxn];

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

void add(int a,int b) {

	pre[++tot]=now[a];

	now[a]=tot,son[tot]=b;

}

void dfs(int fa,int u,int now_odd) {

	if(fake)return;

	if(bo[u]&&odd[u]!=now_odd) {fake=1;return;}

	if(!bo[u]) {odd[u]=now_odd,l[u]=l[fa]-1,r[u]=r[fa]+1;}

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(v!=fa) {

			dfs(u,v,now_odd^1);

			l[u]=max(l[u],l[v]-1);

			r[u]=min(r[u],r[v]+1);

		}

	if(r[u]<l[u])fake=1;

}

void check(int fa,int u,int x) {

	ans[u]=x;

	for(int p=now[u],v=son[p];p;p=pre[p],v=son[p])

		if(v!=fa) {

			if(x-1>=l[v]&&x-1<=r[v])check(u,v,x-1);

			else check(u,v,x+1);

		}

}

int main() {

	n=read();

	for(int i=1;i<n;i++) {

		int x=read(),y=read();

		add(x,y),add(y,x);

	}

	k=read();

	for(int i=1;i<=k;i++) {

		int x=read(),v=read();

		if(i==1)rt=x;bo[x]=1;

		l[x]=r[x]=v,odd[x]=v&1;

	}

	dfs(0,rt,odd[rt]);

	if(!fake) {

		puts("Yes");check(0,rt,l[rt]);

		for(int i=1;i<=n;i++)

			printf("%d\n",ans[i]);

	}

	else puts("No");

	return 0;

}

巴特西

AtCoder Regular Contest 063 E：Integers on a Tree

题目翻译

题解

最新文章

热门文章