E. Construct the Binary Tree(满二叉树-长链构造)

https://codeforces.com/problemset/problem/1311/E

---

 

题意翻译

要求构造一个n个节点的二叉树（每个节点拥有不超过2个孩子），节点1为根，要使所有节点到根的距离之和为d。要求先判断可不可以构造，如果可以输出“YES”，下一行输出2到n号节点的父亲节点，否则输出“NO”。有多组询问。

输入输出样例

输入 #1复制

3
5 7
10 19
10 18

输出 #1复制

YES
1 2 1 3 
YES
1 2 3 3 9 9 2 1 6 
NO

说明/提示

Pictures corresponding to the first and the second test cases of the example:

---

思路：开始极端去想能否满足d的情况，长链n个点会得出n*(n-1)/2距离和，满二叉树的距离和采用线段树的编号和一点dp递推的思路去求。fa[i]=i/2,dp[i]=dp[fa[i]]+1.由此可以得出如果尝试去构造满二叉树但是没有完全构造好的距离和是多少。

然后判完了不满足的情况，尝试每次让总长度+1.这里的构造是用树的最大编号那一条到根的最长链作为基准，然后 从编号大到小遍历，每次把遍历到的节点的父节点改成最长链上同深度的节点。如果最大深度变了，更新一下最大深度。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=6e3;
typedef long long LL;
LL dep[maxn],fa[maxn],a[maxn];
bool vis[maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  dep[1]=0;
  LL t;cin>>t;
  while(t--)
  {
  	LL n,d;cin>>n>>d;
  	memset(vis,0,sizeof(vis));
	LL mx=0;a[0]=1;
  	LL maxsum=n*(n-1)/2;
	if(d>maxsum) {cout<<"NO"<<endl;continue;}
	LL ans=0;
	for(LL i=2;i<=n;i++){
		fa[i]=i/2;dep[i]=dep[fa[i]]+1;ans+=dep[i];mx=max(mx,dep[i]);
	}
	if(d<ans) {cout<<"NO"<<endl;continue;}
	else 
	{
		d-=ans;
		LL x=n;
		while(x>0) a[dep[x]]=x,vis[x]=1,x=fa[x];
		cout<<"YES"<<endl;
		for(LL i=n;i>=1;i--)
		{
			if(vis[i]) continue;
			LL pre=mx;
			while(d&&dep[fa[i]]<pre)
			{
				fa[i]=a[dep[fa[i]]+1];dep[i]=dep[fa[i]]+1;
				if(dep[i]>mx) mx++,a[mx]=i,vis[i]=1;
				d--;
			}
		}
		for(LL i=2;i<=n;i++) cout<<fa[i]<<" ";
		cout<<endl;
	}
  }
return 0;
}