On the subject

Topic link :https://loj.ac/p/2324

The main idea of the topic

give $n$ A tree at a point , The degree of each point does not exceed $3$.

You ask for a binary tree structure （ Root arbitrary choice ） Make the lexicographic order of its traversal smallest .

$1\le n\le 10^6$

Their thinking

It's troublesome to find the root directly , Let's first determine the first point in the middle order traversal .

Obviously, this point is the smallest degree, not $3$ The node of , We set it as $x$.

here $x$ The left subtree of must have no nodes , Then consider that the points it connects are arranged to the right subtree or parent node .

To assume that $x$ What's the degree of this $2$, Because the next step is to traverse $x$ The right subtree , So we first compare the two connected parts as the subtree, what is the first number with the smallest dictionary order .

Because the degree of each point does not exceed $3$, Possible subtrees of the whole picture （ Different roots ） The number of $2n-2$ individual （ Two directions of each side ）, We can preprocess what is the first one with the smallest dictionary order of each subtree .

So we can quickly compare .

Then consider $x$ What's the degree of this $1$ When , Remember that the node it connects is $y$,

• if $y$ The degree is $0$, It's the same everywhere .
• if $y$ The degree is $1$, obviously $y$ You can control the order of the child node and its subtree , Losing the right subtree is definitely the best .
• if $y$ The degree is $2$, The advantage of considering losing a right subtree is that it You can definitely make it Control the order of the left and right subtrees , The advantage of losing the parent node is that you can give priority to $y$ Traverse out , We compare $y$ and $y$ As the first number of the smallest dictionary order in the son time subtree , In this way, we can determine where we lost it .

As for those thrown into the subtree , The above preprocessing can determine the order in the subtree .

Time complexity ：$O(n)$

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n,tot,rt,k[N],f[N][3],g[N][3],t[N][2];
bool v[N];
void dfs(int x,int fa,int p){
    
	if(f[fa][p]<=n+1)return;
	if(k[x]==3)f[fa][p]=n+1;
	else f[fa][p]=x;
	for(int i=0;i<k[x];i++){
    
		int y=g[x][i];
		if(y==fa)continue;dfs(y,x,i);
		f[fa][p]=min(f[fa][p],f[x][i]);
	}
	return;
}
void del(int x,int y){
    
	for(int i=0;i<k[x];i++)
		if(g[x][i]==y){
    
			swap(g[x][i],g[x][k[x]-1]);
			swap(f[x][i],f[x][k[x]-1]);
			k[x]--;
		}
	return;
}
void solve(int x){
    
	rt=x;v[x]=1;
	if(!k[x])return;
	if(k[x]==1){
    
		int y=g[x][0];
		if(k[y]==3&&y<f[x][0])
			del(y,x),t[y][0]=x,solve(y);
		else del(y,x),t[x][1]=y;
	}
	else{
    
		if(f[x][0]>f[x][1])swap(g[x][0],g[x][1]);
		int y=g[x][1];t[x][1]=g[x][0];
		del(y,x);del(g[x][0],x);
		t[y][0]=x;solve(g[x][1]);
	}
	return;
}
void print(int x){
    
	if(!x)return;
	if(v[x]){
    
		print(t[x][0]);
		printf("%d ",x);
		print(t[x][1]);
	}
	else if(k[x]==2){
    
		if(f[x][0]>f[x][1])swap(g[x][0],g[x][1]);
		del(g[x][0],x);print(g[x][0]);
		printf("%d ",x);
		del(g[x][1],x);print(g[x][1]);
	}
	else if(k[x]==1){
    
		if(x<f[x][0])printf("%d ",x);
		del(g[x][0],x);print(g[x][0]);
		if(x>f[x][0])printf("%d ",x);
	}
	else printf("%d ",x);
}
int main()
{
    
	memset(f,0x3f,sizeof(f));
	scanf("%d",&n);tot=1;
	for(int i=1;i<=n;i++){
    
		scanf("%d",&k[i]);
		for(int j=0,x;j<k[i];j++)scanf("%d",&g[i][j]);
	}
	for(int i=1;i<=n;i++)
		for(int j=0;j<k[i];j++)dfs(g[i][j],i,j);
	int x=0;
	for(int i=1;i<=n;i++)
		if(k[i]<=2){
    x=i;break;}
	solve(x);
	print(rt);
	return 0;
}