Codeforces 1246D/1225F Tree Factory (构造)

题目链接

https://codeforces.com/contest/1246/problem/D

题解

首先考虑答案的下界是\(n-1-dep\) (\(dep\)为树的深度，即任何点到根的最大边数)，因为每一次操作只会使一个子树内的点深度\(-1\), 也就最多使得最大深度\(-1\).

那么这个下界能否达到呢？答案是肯定的，因为考虑将过程倒过来，每次选择一个子树将它沿某条边向下移动，对于任何一棵非链的树，最深点到根的路径上一定存在分叉，因此就一定可以通过移动使得最大深度\(+1\).

考虑如何构造: 我的做法是依然倒着思考，DFS整棵树，保证最深点所在子树最后遍历，然后得到的遍历序就是输出的第一个序列。从前往后遍历第一个序列，在第二个答案序列中插入数量等于从上一个点DFS到这个点前进的步数的后一个数。

例如从3号点走到4号点，先后退了\(2\)步又前进了\(3\)步，那么就在第二个答案序列中插入\(3\)个\(4\).

至于算法的正确性，手推一下就很显然了。

代码

#include<bits/stdc++.h>

#define llong long long

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

const int N = 1e5;

struct Edge

{

	int v,nxt;

} e[(N<<1)+3];

int fe[N+3];

int fa[N+3];

int mxd[N+3];

int hvs[N+3];

vector<int> id;

vector<int> opt;

int n,en,cnt;

void addedge(int u,int v)

{

	en++; e[en].v = v;

	e[en].nxt = fe[u]; fe[u] = en;

}

void dfs1(int u)

{

	for(int i=fe[u]; i; i=e[i].nxt)

	{

		int v = e[i].v;

		if(v==fa[u]) continue;

		dfs1(v);

		if(mxd[v]+1>mxd[u]) {mxd[u] = mxd[v]+1,hvs[u] = v;}

	}

}

void dfs2(int u)

{

	id.push_back(u);

	for(int i=1; i<=cnt; i++) opt.push_back(u);

	cnt = 0;

	for(int i=fe[u]; i; i=e[i].nxt)

	{

		int v = e[i].v;

		if(v==fa[u]||v==hvs[u]) continue;

		dfs2(v);

	}

	if(hvs[u]) {dfs2(hvs[u]);}

	cnt++;

}

int main()

{

	scanf("%d",&n);

	for(int i=2; i<=n; i++) {scanf("%d",&fa[i]); fa[i]++; addedge(fa[i],i); addedge(i,fa[i]);}

	dfs1(1);

	dfs2(1);

	for(int i=0; i<id.size(); i++) printf("%d ",id[i]-1); puts("");

	printf("%d\n",opt.size());

	for(int i=0; i<opt.size(); i++) printf("%d ",opt[i]-1); puts("");

	return 0;

}

巴特西

Codeforces 1246D/1225F Tree Factory (构造)

题目链接

题解

代码

最新文章

热门文章