「Codeforces Round 240 div1」E. Mashmokh's Designed Problem - Dfs序/ETT

题目大意

    一颗有$n$个节点的树，根节点始终为$1$，每个节点的若干个子节点有序。你需要进行$m$次操作，操作分为三种：
1.查询两个节点$u,v$之间的距离，每条边的长度均为$1$。
2.给出一个非根节点$u$，断开$u$与其父亲节点的边，将$u$与第$h$个祖先连上一条边并将$u$作为该祖先的最后一个儿子，$u$的父亲是$u$的第一个祖先。
3.查询从根节点出发进行dfs，深度为$k$的点中最后被遍历到的点的编号，根节点的深度为$0$。

---

题目分析

这是一棵真正的动态树，注意到儿子的有序关系以及换子树操作，不难想到使用ETT解决本题。

简单介绍一下ETT：
ETT是动态树的另一种算法，通过展开树的欧拉环游序对树的信息进行维护，支持换子树/换根/修改等操作，可以询问子树信息，不能询问链上信息。

详细的见ETT学习笔记（尚未完稿）。

对于本题，操作1实际上是查询两点的LCA，因为欧拉环游序的性质，我们可以查询两点间深度最小的点即为LCA。
操作2是裸的换子树操作。
操作3就有点玄妙了，我们可以通过数据结构（平衡树）上的二分解决这个问题。

注意到询问的满足条件最后一个点，不难想到二分，平衡树维护一个子树深度最大值和最小值，因为欧拉环游序的深度不会突变，因此有单调性，我们可以这样二分：
首先判断右子树是否满足条件（是否有一个满足深度条件的点），若有递归右子树，否则判断当前点是否是要求的点，若是则返回，否则递归左子树。

这样我们就可以解决这个问题了。

再具体实现的时候，我们也可以不使用欧拉环游序，使用非压缩的欧拉括号序同样可以解决，只是查询LCA的时候是最小深度$-1$的点。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=200005;

int n,q,First[maxn],Last[maxn],step=2;
vector<int>edges[maxn];

struct Tree {
	int child[2],father;
	int key,small,big,depth,lazy,id;
	Tree() {}
	Tree(int l,int r,int fa,int k,int d,int _id):father(fa),key(k),small(d),big(d),depth(d),lazy(0),id(_id) {
		child[0]=l;
		child[1]=r;
	}
};
struct Splay {
	int size,root;
	Tree tree[maxn];
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define fa(x) tree[x].father
#define val(x) tree[x].key
#define lazy(x) tree[x].lazy
#define depth(x) tree[x].depth
	Splay() {
		tree[++size]=Tree(0,2,0,-INT_MAX,0,0);
		tree[size].small=INT_MAX,tree[size].big=-INT_MAX;
		tree[++size]=Tree(0,0,1,INT_MAX,0,0);
		tree[size].small=INT_MAX,tree[size].big=-INT_MAX;
		root=size;
	}
	void clear(int index) {
		tree[index]=Tree(0,0,0,0,0,0);
	}
	bool checkson(int index) {
		return rs(fa(index))==index;
	}
	void modify(int index,int v) {
		lazy(index)+=v;
		if(index<=2)return;
		depth(index)+=v;
		tree[index].small+=v;
		tree[index].big+=v;
	}
	void push_down(int index) {
		if(!lazy(index))return;
		if(ls(index))modify(ls(index),lazy(index));
		if(rs(index))modify(rs(index),lazy(index));
		lazy(index)=0;
	}
	void push_up(int index) {
		if(!index)return;
		if(index<=2)tree[size].small=INT_MAX,tree[size].big=-INT_MAX;
		else tree[index].small=tree[index].big=depth(index);
		if(ls(index)) {
			tree[index].small=min(tree[index].small,tree[ls(index)].small);
			tree[index].big=max(tree[index].big,tree[ls(index)].big);
		}
		if(rs(index)) {
			tree[index].small=min(tree[index].small,tree[rs(index)].small);
			tree[index].big=max(tree[index].big,tree[rs(index)].big);
		}
	}
	void rotate(int index) {
		int father=fa(index),grand=fa(father),side=checkson(index);
		if(grand)tree[grand].child[checkson(father)]=index;
		tree[father].child[side]=tree[index].child[side^1];
		fa(tree[father].child[side])=father;
		fa(father)=index;
		tree[index].child[side^1]=father;
		fa(index)=grand;
		push_up(father);
		push_up(index);
	}
	void splay(int index,int target=0) {
		push_down(index);
		for(int father; (father=fa(index))!=target; rotate(index)) {
			int grand=fa(father);
			if(grand)push_down(grand);
			push_down(father);
			push_down(index);
			if(fa(father)!=target)rotate(checkson(index)==checkson(father)?father:index);
		}
		if(target==0)root=index;
	}
	int insert(int v,int d,int id) {
		int now=root,father=0;
		while(now&&val(now)!=v) {
			father=now;
			now=tree[now].child[val(now)<v];
		}
		tree[now=++size]=Tree(0,0,father,v,d,id);
		if(father)tree[father].child[val(father)<v]=now;
		splay(now);
		return now;
	}
	int pre_suc(int bj) {
		push_down(root);
		int now=tree[root].child[bj];
		while(tree[now].child[bj^1])push_down(now),now=tree[now].child[bj^1];
		push_down(now);
		return now;
	}
	int Find(int index,int d) {
		while(true) {
			push_down(index);
			if(rs(index)&&tree[rs(index)].small<=d&&tree[rs(index)].big>=d)index=rs(index);
			else if(tree[index].depth==d)return index;
			else index=ls(index);
		}
	}
	int dist(int x,int y) {
		if(x==y)return 0;
		splay(First[x]);
		splay(First[y],root);
		int pos=tree[First[y]].child[checkson(First[y])^1];
		int ans=pos?tree[pos].small-1:INT_MAX;
		ans=min(ans,min(depth(First[x]),depth(First[y])));
		return depth(First[x])+depth(First[y])-2*ans;
	}
	void change(int x,int y) {
		splay(First[x]);
		int p=tree[Find(ls(First[x]),depth(First[x])-y)].id; //找到目标结点
		//分离
		int pre=pre_suc(0);
		splay(Last[x]);
		int suc=pre_suc(1);
		splay(pre);
		splay(suc,pre);
		int pos=ls(suc);
		push_down(pre),push_down(suc); //传递残余标记
		int num=-depth(pre)-(pre==First[tree[pre].id]); //若是其父亲还要-1
		fa(pos)=ls(suc)=0;
		push_up(suc),push_up(pre);
		//拼接
		splay(Last[p]);
		pre=pre_suc(0);
		splay(pre);
		splay(suc=Last[p],pre);
		push_down(pre),push_down(suc); //先传递标记，否则会影响新加入的子树
		num+=depth(pre)+(pre==First[tree[pre].id]);
		ls(suc)=pos;
		fa(pos)=suc;
		modify(pos,num);
		push_up(suc);
		push_up(pre);
	}
} bbt;

void AddEdge(int x,int y) {
	edges[x].push_back(y);
}

void Dfs(int Now,int depth) {
	First[Now]=++step;
	bbt.insert(step,depth,Now);
	for(int Next:edges[Now])Dfs(Next,depth+1);
	Last[Now]=++step;
	bbt.insert(step,depth,Now);
}
	
int main() {
	n=Get_Int();
	q=Get_Int();
	for(int i=1; i<=n; i++) {
		int x=Get_Int();
		while(x--)AddEdge(i,Get_Int());
	}
	Dfs(1,1);
	while(q--) {
		int opt=Get_Int(),x=Get_Int();
		if(opt==1)printf("%d\n",bbt.dist(x,Get_Int()));
		else if(opt==2)bbt.change(x,Get_Int());
		else printf("%d\n",bbt.tree[bbt.Find(bbt.root,x+1)].id);
	}
	return 0;
}