CF1278E Tests for problem D 做题记录

给一棵 $n$ 个点的树，构造 $n$ 条线段，要求每个端点都是 $[1,2n]$ 中的整数且不重复，并使得两个点 $i,j$ 在树上有边，当且仅当线段 $i,j$ 相交且不包含。

$1 \le n \le 5 \cdot 10^5$。

不难发现两个区间相交但不包含只有两种情况：$x$ 在 $y$ 左边或者 $y$ 在 $x$ 左边，那么不妨钦定 $u$ 的区间在它父亲 $fa$ 的区间右边和 $fa$ 的区间相交，在左边和它儿子 $v$ 的区间相交，构造这样的东西：（红框是递归构造下去的儿子的子树）

这样递归构造一定是合法的，设节点 $u$ 的儿子个数为 $son_u$，那么 $u$ 的区间除去属于它父亲和兄弟的部分后长度只有 $son_u+1$，刚好够连接 $u$ 的所有儿子，所以没有任何位置浪费。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=1000005;

int n;
int esum,to[S],nxt[S],h[S];
int rig,l[S],r[S];

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

void dfs(int u,int fa)
{
	int cnt=0;
	for(int i=h[u];i;i=nxt[i]) cnt+=to[i]!=fa;
	rig=r[u]=rig+cnt+1;
	int lft=rig;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa) continue;
		l[v]=--lft;
		dfs(v,u);
	}
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	rig=l[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++) printf("%d %d\n",l[i],r[i]);
	return 0;
}