【FJWC 2019】森林

样例输入

0

5

1 0 0 2

样例输出

1

2

3

3

我们发现，答案就是直径加上直径上某个点出发，不经过其他直径上的点的最长链。这里的直径可以是任意一条直径。

首先我们每次只加一个点，所以我们很好维护新的直径。假设旧直径的两个端点是\((A,B)\)，则加入点\(X\)后新的端点可能是\((A,B),(A,X),(B,X)\)。

然后我们考虑求“直径上某个点出发，不经过其他直径上的点的最长链”。

我们知道，\(Lct\)有虚边和实边。我们给每个节点开一个\(multiset\)维护虚子树贡献的最长链。

我们记录\(mx_v\)表示\(v\)所在\(splay\)中所有虚儿子贡献的最长链。\(lmx_v\)表示\(v\)所在\(splay\)的从最左端点出发，经过一段实边，再经过一段虚边的最长路径；\(rmx_v\)同理。

很显然，\(v\)所在这条实链的顶端到子树内的最长链就是\(lmx_v\)。记录\(lmx_v\)是为了在\(access\)操作的时候维护向其父亲贡献的最长链。

我们询问的时候就先\(MakeRoot(A)\),再\(access(B)\)，这样\(A\to B\)的直径在一条实链上，答案就是\(dis_{A,B}+mx_A-[mx_A!=0]\)。

因为有\(MakeRoot\)操作，所以我们要维护\(rmx\)，\(reverse\)的时候还要交换\(lmx,rmx\)。

可以参考【清华集训2016】数据交互

注意：\(push\_down(v)\)的时候要将左右儿子的\(lmx\)和\(rmx\)也交换了，否则\(update\)的时候会出错。

代码：

#include<bits/stdc++.h>

#define ll long long

#define N 400005

using namespace std;

inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

multiset<int>st[N];

int n;

int ans;

int A,B;

int rev[N],fa[N],ch[N][2];

int lmx[N],rmx[N],mx[N];

int size[N];

#define ls ch[v][0]

#define rs ch[v][1]

void update(int v) {

	size[v]=size[ls]+size[rs]+1;

	mx[v]=max(*(--st[v].end()),max(mx[ls],mx[rs]));

	lmx[v]=*(--st[v].end())+size[ls];

	rmx[v]=*(--st[v].end())+size[rs];

	lmx[v]=max(lmx[v],lmx[ls]);

	rmx[v]=max(rmx[v],rmx[rs]);

	if(rs) lmx[v]=max(lmx[v],lmx[rs]+size[ls]+1);

	if(ls) rmx[v]=max(rmx[v],rmx[ls]+size[rs]+1);

}

void Rev(int v) {

	rev[v]^=1;

	swap(ls,rs);

	swap(lmx[v],rmx[v]);

}

void down(int v) {

	if(rev[v]) {

		/*************/

		Rev(ls);

		Rev(rs);

		rev[v]=0;

	}

}

bool isroot(int v) {return v!=ch[fa[v]][0]&&v!=ch[fa[v]][1];}

void rot(int v) {

	int f=fa[v],gr=fa[f];

	int sn=v==ch[f][1],son=ch[v][!sn];

	if(!isroot(f)) ch[gr][f==ch[gr][1]]=v;

	ch[f][sn]=son;

	ch[v][!sn]=f;

	if(son) fa[son]=f;

	fa[v]=gr;

	fa[f]=v;

	update(f);

	update(v);

}

void Splay(int v) {

	static int st[N],top;

	top=0;

	st[++top]=v;

	for(int i=v;!isroot(i);i=fa[i]) st[++top]=fa[i];

	while(top) down(st[top--]);

	while(!isroot(v)) {

		int f=fa[v],gr=fa[f];

		if(!isroot(f)) rot(v==ch[f][1]^f==ch[gr][1]?v:f);

		rot(v);

	}

}

void Insert(int v,int f) {st[f].insert(lmx[v]+1);}

void Del(int v,int f) {st[f].erase(st[f].find(lmx[v]+1));}

void access(int v) {

	int tem=0;

	while(v) {

		Splay(v);

		if(tem) Del(tem,v);

		if(rs) Insert(rs,v);

		rs=tem;

		update(v);

		tem=v;

		v=fa[v];

	}

}

void Make_root(int v) {

	access(v);

	Splay(v);

	Rev(v);

}

void Link(int v,int f) {

	update(v);

	access(f);

	Splay(f);

	fa[v]=f;

	Insert(v,f);

	update(f);

}

namespace DIS {

	int dep[N],fa[N][20];

	int mxdis=0;

	int lca(int a,int b) {

		if(dep[a]<dep[b]) swap(a,b);

		for(int i=18;i>=0;i--)

			if(fa[a][i]&&dep[fa[a][i]]>=dep[b])

				a=fa[a][i];

		if(a==b) return a;

		for(int i=18;i>=0;i--)

			if(fa[a][i]!=fa[b][i])

				a=fa[a][i],b=fa[b][i];

		return fa[a][0];

	}

	int dis(int a,int b) {return dep[a]+dep[b]-2*dep[lca(a,b)];}

	void Insert(int v,int f) {

		fa[v][0]=f;

		for(int i=1;i<=18;i++) fa[v][i]=fa[fa[v][i-1]][i-1];

		dep[v]=dep[f]+1;

		int da=dis(A,v),db=dis(B,v);

		mxdis=max(mxdis,max(da,db));

		if(da==mxdis) B=v;

		else if(db==mxdis) A=v;

	}

}

int main() {

	int cas=Get();

	n=Get();

	for(int i=1;i<=n;i++) st[i].insert(0);

	A=B=1;

	for(int i=2;i<=n;i++) {

		int a=Get()^ans;

		DIS::Insert(i,a);

		Link(i,a);

		Make_root(A);

		access(B);

		Splay(B);

		cout<<(ans=DIS::mxdis+mx[B]-(mx[B]!=0))<<"\n";

	}

	return 0;

}

巴特西

【FJWC 2019】森林

【FJWC 2019】森林

样例输入

样例输出

最新文章

热门文章

巴特西

【FJWC 2019】 森林

【FJWC 2019】 森林

样例输入

样例输出

最新文章

热门文章

【FJWC 2019】森林

【FJWC 2019】森林