【2019 NWERC B】Balanced Cut 题解

题目大意

  给定一棵 $n$ 个点的 AVL 树（点权恰好为 $1$ 到 $n$），你需要选择其中的 $k$ 个点，满足：

1. 如果要选一个点，那么它的祖先也必须选。也就是选出来的 $k$ 个点会组成一棵新的树。
2. 这棵新的树也必须是 AVL 树。

  （放个传送门里面有图片可以看看例子

  每种选法可以表示为一个长度为 $n$ 的 01 串（表示每个点选或不选），你需要求出字典序最大的方案。

  $1 \leq k \leq n \leq 5 \times 10^5$
  4s，256MB

题解

  做这种全服个位数通过的题其实挺有快感的

  首先大的框架肯定是贪心，从小到大 check 每个点能不能选。

  check 的依据就是两点：会不会跟已选的点冲突，会不会必需结点数目超过 $k$ 的限制。AVL 树的一个性质是，树高是 $O(\log n)$ 的。基于这个我们可以设计出一个粗略的 check 的方法：
  （$lson,rson$ 表示一个结点的左右儿子）
  设要 check $s$ 这个点，从 $s$ 开始不断往父亲跳，维护当前子树最少要选的点数 $nownum$，以及所选的层数 $nowdeep$。假设当前点是 $x$，父亲为 $y$。
  若 $x$ 是 $y$ 的右儿子，则 $y$ 的左儿子肯定已经全部考虑过了，定死了不能变了，所以只需判断这俩兄弟的层数差是否在 $1$ 以内即可，然后更新 $nowdeep$ 和 $nownum$；
  若 $x$ 是 $y$ 的左儿子，则 $y$ 的右儿子肯定全都没考虑，我们预处理一个 dp 数组 $f_{i,j}$ 表示以 $i$ 为根的子树选 $j$ 层的最少花费，那么这时只需要使 $nownum$ 加上 $f_{rson_y,nowdeep-1}$ 即可。
  最后判断 $nownum \leq k$ 即是合法。

  会有一些问题：当 $x$ 是 $y$ 左儿子时，$y$ 的右儿子可能曾经被 $x$ 子树里的其他结点提出过更大的层数要求，记为 $tag_{rson_y}$，是的这其实就是一个不断打 tag 的过程，所以实际上右儿子要选的层数应该是 $f_{rson_y,\max\{nowdeep-1,tag_{rson_y}\}}$。
  然后，当 check 一个点成功时，它必须沿着祖先链上去给所有右兄弟更新 tag。

  这时又会有新的问题：当前结点 $x$ 本身可能会有一个 $tag_x$ 的任务，然而我们为了使点数最少我们一直都只选必需的点，这导致 $nowdeep$ 可能完不成 $tag_x$ 这个任务，我们就需要计算现在 $nowdeep$ 层补到 $tag_x$ 层需要额外付出多少代价。
  记 $h_i (i \ge nowdeep)$ 表示当前子树从选 $nowdeep$ 层追加到选 $i$ 层需要额外补多少代价。这个东西也很好维护，当 $nowdeep$ 变大成 $nowdeep'$ 时，所有的 $h_i-=h_{nowdeep'}$；当往上跳遇到右兄弟时，再维护 $h_i=\min\{h_{i-1}+f_{rson,i}-f_{rson,t},~h_i+f_{rson,i-1}-f_{rson,t}\}$。（其中 $t=\max\{nowdeep-1,tag_{rson}\}$，因为我们维护的是额外补的差价，而 $f_{rson,t}$ 是已经付出的）

  时间复杂度：每个点往上跳是 $O(\log n)$ 步的，每跳一次维护一下 $h$ 数组又是 $O(\log n)$ 的，因此总的是 $O(n \log^2 n)$。但它跑得飞快，甚至这题其他人写的像是 $O(n \log n)$ 的（我都没看懂）用时是我的若干倍。。

  （另外有些小技巧，比如如果一个点它的(左)子树中有人确定要选了，那么它作为祖先就一定要选，就不用 check 了，这样的话任何要 check 的点都必然是左子树不选的，于是各变量的初值也方便多了。。

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=5e5+5, MX=30;
const int inf=522133279;

int n,k,root,son[maxn][2],p[maxn];

int f[maxn][MX+2],nmax[maxn],deep[maxn];
void dfs_dp(int k)
{
	nmax[k]=k;
	int l=son[k][0], r=son[k][1];
	if (l)
	{
		deep[l]=deep[k]+1;
		dfs_dp(l);
	}
	if (r)
	{
		deep[r]=deep[k]+1;
		dfs_dp(r);
		nmax[k]=max(nmax[k],nmax[r]);
	}
	f[k][1]=1;
	fo(j,2,MX) f[k][j]=min(f[k][j],min(f[l][j-1]+f[r][j-2],f[l][j-2]+f[r][j-1])+1);
}

int tag[maxn],maxdeep[maxn],num[maxn],h[MX+2];
void Make_tag(int st)
{
	for(int x=st; x!=-1; x=p[x])
	{
		maxdeep[x]=max(maxdeep[x],deep[st]);
		num[x]++;
		int y=p[x];
		if (y!=-1 && son[y][0]==x) tag[son[y][1]]=max(tag[son[y][1]],maxdeep[x]-1-deep[y]);
	}
}
bool check(int x)
{
	if (num[x]) return 1;
	int nowdeep=0, nownum=0;
	memset(h,31,sizeof(h));
	h[0]=f[son[x][1]][0], h[1]=f[son[x][1]][1];
	for(; x!=-1; x=p[x])
	{
		int y=p[x];
		nownum++;
		if (nowdeep+1<tag[x])
		{
			nownum+=h[nowdeep=tag[x]-1];
			if (nownum>=inf) return 0;
			fd(i,MX,nowdeep) if (h[i]<inf) h[i]-=h[nowdeep];
		}
		nowdeep++;
		fd(i,MX,nowdeep) h[i]=h[i-1];
		if (y!=-1 && son[y][0]==x && son[y][1])
		{
			int r=son[y][1], t=max(tag[r],nowdeep-1);
			if (f[r][t]>=inf) return 0;
			nownum+=f[r][t];
			fd(i,MX,nowdeep+1)
			{
				h[i]=min(h[i-1]+f[r][i]-f[r][t],h[i]+f[r][i-1]-f[r][t]);
				if (h[i]>n) h[i]=inf;
			}
			h[nowdeep]=0;
		} else if (y!=-1 && son[y][1]==x && son[y][0])
		{
			int l=son[y][0];
			if (nowdeep-(maxdeep[l]-deep[y])>1) return 0;
			nowdeep=max(nowdeep,maxdeep[l]-deep[y]);
			h[nowdeep]=0;
			nownum+=num[son[y][0]];
		}
	}
	return nownum<=k;
}

bool ans[maxn];
int main()
{
	scanf("%d %d",&n,&k);
	fo(i,1,n)
	{
		scanf("%d",&p[i]);
		if (p[i]==-1) root=i; else son[p[i]][(i>p[i])]=i;
	}
	
	memset(f,31,sizeof(f));
	fo(i,0,n) f[i][0]=0;
	deep[root]=1;
	dfs_dp(root);
	
	fo(i,1,n) if (check(i))
	{
		ans[i]=1;
		Make_tag(i);
	}
	
	fo(i,1,n) putchar(ans[i] ?'1' :'0');
	puts("");
}