LOJ2324「清华集训 2017」小Y和二叉树

题目链接

瞎jb贪一发就过了。首先度数<=2且编号最小的点一定是中序遍历最靠前的点，我们从这个点开始dfs一遍算出子树中度数<=2且编号最小的点记为\(f(i)\)，然后从这个点开始一步一步确定出它到根的路径。

如果这个点度数还剩2(也就是除掉之前确定的左儿子后的度数)，那么选\(f(i)\)小的作为右儿子，如果度数剩1，那么比较\(f(i)\)与i谁更小，若\(i<=f(i)\)则把i作为父亲否则作为右儿子。每次不断跳到它的父亲，没父亲了就是根了，之后的事就是把这条链上的每个点的右儿子的子树给确定出来，这个算出\(f(i)\)后搞一搞就行了，注意i只有一个儿子时若\(i<f(ch)\)那么把这个ch调到右边去。

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<vector>

#include<algorithm>

#include<cmath>

#define P puts("lala")

#define cp cerr<<"lala"<<endl

#define ln putchar('\n')

#define pb push_back

#define fi first

#define se second

#define mkp make_pair

using namespace std;

inline int read()

{

    char ch=getchar();int g=1,re=0;

    while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();}

    while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar();

    return re*g;

}

typedef long long ll;

typedef pair<int,int> pii;

const int N=1000050;

const int inf=0x3f3f3f3f;

int deg[N],head[N],cnt=0;

pii oo=pii(inf,inf);

struct node

{

	int to,next;

}e[N<<1];

inline void add(int x,int y)

{

	e[++cnt]=(node){y,head[x]};head[x]=cnt;

}

int n,f[N],ch[N][2],g[N];

void dfs(int u,int fa)

{

	pii minn=oo,sec=oo;

	for(int i=head[u];i;i=e[i].next)

	{

		int v=e[i].to;

		if(v==fa) continue;

		dfs(v,u);

		if(pii(f[v],v)<minn)

		{

			if(minn<sec) sec=minn;

			minn=pii(f[v],v);

		}

		else if(pii(f[v],v)<sec) sec=pii(f[v],v);

	}

	if(minn==oo) f[u]=u,ch[u][0]=ch[u][1]=0;

	else if(sec==oo)

	{

		if(u<minn.fi) ch[u][0]=0,ch[u][1]=minn.se,f[u]=u;

		else ch[u][0]=minn.se,ch[u][1]=0,f[u]=minn.fi;

	}

	else ch[u][0]=minn.se,ch[u][1]=sec.se,f[u]=minn.fi;

}

void dfs2(int u,int fa)

{

	int tot=-1;

	g[u]=inf;

	if(deg[u]<=2) g[u]=u;

	for(int i=head[u];i;i=e[i].next)

	{

		int v=e[i].to;

		if(v==fa) continue;

		dfs2(v,u);

		ch[u][++tot]=v;

		g[u]=min(g[u],g[v]);

	}

	if(tot==1&&g[ch[u][1]]<g[ch[u][0]]) swap(ch[u][0],ch[u][1]);

	else if(tot==0&&g[ch[u][0]]>=ch[u][0]) ch[u][1]=ch[u][0],ch[u][0]=0;

}

void print(int o)

{

	if(ch[o][0]) print(ch[o][0]);

	printf("%d ",o);

	if(ch[o][1]) print(ch[o][1]);

}

void wj()

{

#ifndef ONLINE_JUDGE

	freopen("binary.in","r",stdin);

	freopen("binary.out","w",stdout);

#endif

}

int main()

{

	wj();

	int i,j,opt,T;

	n=read();

	int minx=inf;

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

	{

		deg[i]=read();

		for(j=1;j<=deg[i];++j) add(i,read());

		if(deg[i]<=2&&i<minx) minx=i;

	}

	dfs2(minx,0);

	int u=minx;

	while(u)

	{

		if(ch[u][0]) dfs(ch[u][0],u);

		u=ch[u][1];

	}

	u=minx;

	while(u)

	{

		printf("%d ",u);

		if(ch[u][0]) print(ch[u][0]);

		u=ch[u][1];

	}

	return 0;

}

巴特西

LOJ2324「清华集训 2017」小Y和二叉树

最新文章

热门文章