CF1670E Hemose on the Tree 做题记录

题目包含 $Q$ 组数据。

对于每一组数据，给出 $p$，使得 $n=2^p$，给出一棵 $n$ 个点的树的边，你要定出树的根，和树上的所有点权和边权，使得所有点权和边权构成一个 $1 \sim 2 n - 1$ 的排列，且从根到每个节点和每条边的简单路径上点权和边权的异或和的最大值最小。输出方案。

$1\le p\le 17$。

首先显然答案下界是 $2^p$，因为无论如何都至少有一条简单路径的异或和二进制第 $p$ 位为 $1$。

那么不妨猜测能取到下界，尝试构造并证明之。

不妨设根为 $1$，令 $a_1=2^p$，接下来往下递归：

• 若此时异或和为 $2^p$，那么让边权为 $2^p+c$（$c$ 是一个常数），子节点点权为 $c$，让异或和变成 $0$；
• 若此时异或和为 $0$，那么让边权为 $c$，子节点点权为 $2^p+c$，让异或和变成 $2^p$；

不难发现，这样构造除了根之外的所有节点都需要不同的 $c$，由于不同的 $c$ 共有 $n-1$ 个，所以刚好够。

代码如下：

// Problem: CF1670E Hemose on the Tree
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1670E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=500005;

int p,n;
int esum,to[S],id[S],nxt[S],h[S];
int c;
int a[S],b[S];

inline void add(int x,int y,int idx)
{
	to[++esum]=y;
	id[esum]=idx;
	nxt[esum]=h[x];
	h[x]=esum;
}

void dfs(int u,int fa,bool isn)
{
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		c++;
		b[id[i]]=c+(isn?n:0);
		a[v]=c+(isn?0:n);
		dfs(v,u,!isn);
	}
}

void slove()
{
	scanf("%d",&p);
	n=1<<p;
	esum=0;
	for(int i=1;i<=n;i++) h[i]=0;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y,i),add(y,x,i);
	}
	a[1]=n;
	c=0;
	dfs(1,0,true);
	puts("1");
	for(int i=1;i<=n;i++) printf("%d ",a[i]);
	printf("\n");
	for(int i=1;i<=n-1;i++) printf("%d ",b[i]);
	printf("\n");
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}