题目大意
要求你维护一棵树，支持以下操作
- 询问 $(u,v)$ 两点之间的距离
- 将 $v$ 的祖先变成它的 $k$ 级祖先
- 询问深度为 $d$ 的点中最靠右的点是啥。
每层一开始的位置关系在输入中给出 每次 $2$ 操作的时候默认插入到子节点中的最右边。
题解
学了个叫做维护括号序列的东西。。（不知道是不是叫ETT？）
括号序列就是在这个点入栈和出栈的时候都记录一次，比如样例1的括号序列就是 12344321。我们记第 $i$ 个点入栈的位置和出栈的位置分别为 $in_i,out_i$。括号序列的一些性质：
$(in[u],in[v])$ 中未匹配的括号都是路径上除lca和端点以外的点
这个看起来并不是很好维护 于是我们考虑放缩一下 得到另外一个结论
$(in[u],in[v])$ 中的节点的最小值一定是 $lca$ 的儿子。
那么 $1$ 就很好维护了。我们考虑如何维护操作 $2$：发现在括号序列上实现子树移动是很方便的 子树对应的是一段区间 用Splay维护即可。
$3$ 操作可以记录最大值最小值，直接在splay上二分。代码还是很长的
#include<bits/stdc++.h>
#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 3e5 + 5;
std::vector<int> G[MAXN];
int in[MAXN],out[MAXN],dep[MAXN],id[MAXN],ts;
int n;
inline void dfs(int v,int d){
in[v] = ++ts;id[ts] = v;dep[ts] = d;
for(auto x:G[v]) dfs(x,d+1);
out[v] = ++ts;id[ts] = v;dep[ts] = d;
}
int f[MAXN],mn[MAXN],mx[MAXN],tag[MAXN],ch[MAXN][2],sz[MAXN];
#define lc (ch[x][0])
#define rc (ch[x][1])
inline void pushup(int x){
if(!x) return;
mn[x] = std::min(dep[x],std::min(mn[lc],mn[rc]));
mx[x] = std::max(dep[x],std::max(mx[lc],mx[rc]));
sz[x] = sz[lc]+sz[rc]+1;
}
inline void cover(int x,int d){
mn[x] += d;mx[x] += d;tag[x] += d;dep[x] += d;
}
inline void pushdown(int x){
if(tag[x]){
if(lc) cover(lc,tag[x]);
if(rc) cover(rc,tag[x]);
tag[x] = 0;
}
}
inline void rotate(int x){
int y = f[x],z = f[y],k = ch[y][1]==x,w = ch[x][!k];
ch[z][ch[z][1]==y] = x;f[x] = z;
ch[x][!k] = y;f[y] = x;
ch[y][k] = w;if(w) f[w] = y;
pushup(y);pushup(x);
}
int rt;
int st[MAXN];
inline void splay(int x,int v=0){
int y = x,z;
st[z = 1] = y;
while(f[y] != v) st[++z] = y = f[y];
while(z) pushdown(st[z--]);
while((y=f[x]) != v){
if((z=f[y]) != v) rotate((ch[z][1]==y)^(ch[y][1]==x) ? x : y);
rotate(x);
}
if(!v) rt = x;
pushup(x);
}
inline int getk(int k){
int x = rt;
while(true){
pushdown(x);
if(k <= sz[lc]) x = lc;
else if(k == sz[lc]+1) return splay(x),x;
else k -= sz[lc]+1,x = rc;
}
}
inline int pre(int x){
splay(x);x = lc;while(rc) x = rc;return x;
}
inline int suf(int x){
splay(x);x = rc;while(lc) x = lc;return x;
}
inline int split(int x,int y){
x = pre(x);y = suf(y);
splay(x);splay(y,x);return ch[y][0];
}
inline int find(int x,int k){
pushdown(x);
if(mn[rc] <= k && k <= mx[rc]) return find(rc,k);
if(dep[x] == k) return splay(x),x;
return find(lc,k);
}
inline void build(int f,int &x,int l,int r){
if(l > r) return;
x = (l+r)>>1;mn[x] = mx[x] = dep[x];sz[x] = 1;tag[x] = 0;::f[x] = f;
if(l == r) return;
build(x,lc,l,x-1);build(x,rc,x+1,r);
pushup(x);
}
inline void dfs(int x){
pushdown(x);
if(lc) dfs(lc);
printf("(%d,%d)",id[x],dep[x]);
if(rc) dfs(rc);
pushup(x);
}
int main(){
mn[0] = 1e9;int m;scanf("%d%d",&n,&m);
FOR(i,1,n){
int k;scanf("%d",&k);
while(k--) {int x;scanf("%d",&x);G[i].pb(x);}
}
dfs(1,1);build(0,rt,1,ts);
while(m--){
int opt;scanf("%d",&opt);
if(opt == 1){
int u,v;scanf("%d%d",&u,&v);int res = 0;
splay(in[u]);int rku = sz[ch[in[u]][0]]+1;res += dep[in[u]];//询问单点前一定要splay到根 防止标签未下传
splay(in[v]);int rkv = sz[ch[in[v]][0]]+1;res += dep[in[v]];
// DEBUG(res);
if(rku > rkv) std::swap(u,v);
int t = split(suf(in[u]),pre(out[v]));res -= 2*(mn[t]-1);// 括号序[in[u],out[v]]保存了除lca外的路径上的点
printf("%d\n",res);
}
if(opt == 2){
int v,h;scanf("%d%d",&v,&h);
splay(in[v]);int fa = id[find(ch[in[v]][0],dep[in[v]]-h)];
int t = split(in[v],out[v]);pushdown(f[t]);ch[f[t]][0] = 0;pushup(f[t]);pushup(f[f[t]]);f[t] = 0;
cover(t,1-h);int tt = pre(out[fa]);splay(tt);splay(out[fa],tt);
pushdown(out[fa]);ch[out[fa]][0] = t;f[t] = out[fa];pushup(out[fa]);pushup(tt);
}
if(opt == 3){
int k;scanf("%d",&k);splay(1);++k;
printf("%d\n",id[find(1,k)]);
}//dfs(rt);puts("");
}
return 0;
}