@codeforces - 414E@ Mashmokh's Designed Problem

古城微笑少年丶 2023-06-01 12:59 5阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定一棵 n 个点的树，每个点的儿子是有序的。  
现给定 m 次操作，每次操作是下列三种中的一种：

（1）给定 u, v，询问 u, v 之间的距离。  
（2）给定 v, h，断开 v 到父亲的边，将 v 这棵子树加入到它的第 h 个祖先的最后一个儿子。  
（3）给定 k，询问在当前这棵树上 dfs 后得到 dfs 序中，最后一个深度为 k 的点的编号。

**Input**  
第一行包含两个整数 n, m (2 ≤ n ≤ 10^5; 1 ≤ m ≤ 10^5)，表示点数与询问数。  
接下来 n 行每行一个 li，表示 i 号结点的儿子个数。紧接着输入 li 个整数，第 j 个整数表示 i 的第 j 个儿子编号（再次强调儿子是有序的）。  
接下来 m 行每行形如 "1 v u", "2 v h", 或 "3 k"。第一个数描述操作种类，接下来描述了这个操作的参数。  
保证操作合法。

**Output**  
对于 1, 3 询问，输出其对应的答案。

**Examples**  
**Input1**  
4 9  
1 2  
1 3  
1 4  
0  
1 1 4  
2 4 2  
1 3 4  
3 1  
3 2  
2 3 2  
1 1 2  
3 1  
3 2  
**Output1**  
3  
2  
2  
4  
1  
3  
4

**Input2**  
2 2  
1 2  
0  
1 2 1  
3 1  
**Output2**  
1  
2

## @solution@ ##

看到连边删边很自然地想到 lct，然而 lct 并没有办法很好地维护询问 3。。。  
考虑对于连边删边的另一种处理方法：使用平衡树维护括号序，剪切某棵子树对应的序列与拼接某棵子树对应的序列即可。

然而它要求两点距离？那我们类比一下括号序，使用平衡树维护一下欧拉序即可（就是可以把 lca 问题转为 rmq 问题的那个东东）。

对于询问 1，我们提取出 u, v 之间的区间，查询里面 dep 的最小值 x，用 dep\[u\] + dep\[v\] - 2\*x 即可。  
对于询问 3，我们可以发现欧拉序相邻位置的深度是连续的。所以我们可以存储 dep 的最小值与 dep 的最大值来判断一棵子树内是否含有某个特定 dep 的值。  
对于操作 2，我们首先要定位 x 的第 h 个祖先。可以提取出以 x 为结尾的序列前缀，在这个前缀上找最后一个深度为 dep\[x\]-h 的点——其实就是询问 3。然后剪切，拼接，把 x 的子树内所有点的深度减去一个量（打 tag 就好了）。

总复杂度就是 splay 的复杂度 O(nlogn)。

## @accepted code@ ##

#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int MAXN = 200000; struct Splay{ struct node{ node *fa, *ch[2]; int num, key, mx, mn, tg; }pl[2*MAXN + 5], *root, *NIL; Splay() { root = NIL = &pl[0]; NIL->ch[0] = NIL->ch[1] = NIL->fa = NIL; NIL->mx = -MAXN, NIL->mn = MAXN, NIL->tg = 0; } void set_child(node *x, node *y, int d) { if( x != NIL ) x->ch[d] = y; if( y != NIL ) y->fa = x; } void pushdown(node *x) { if( x->tg ) { if( x->ch[0] != NIL ) x->ch[0]->key += x->tg, x->ch[0]->mx += x->tg, x->ch[0]->mn += x->tg, x->ch[0]->tg += x->tg; if( x->ch[1] != NIL ) x->ch[1]->key += x->tg, x->ch[1]->mx += x->tg, x->ch[1]->mn += x->tg, x->ch[1]->tg += x->tg; x->tg = 0; } } void pushup(node *x) { x->mn = min(x->key, min(x->ch[0]->mn, x->ch[1]->mn)); x->mx = max(x->key, max(x->ch[0]->mx, x->ch[1]->mx)); } void rotate(node *x) { node *y = x->fa; int d = (y->ch[1] == x); pushdown(y), pushdown(x); if( y->fa != NIL ) set_child(y->fa, x, y->fa->ch[1] == y); else x->fa = y->fa; set_child(y, x->ch[!d], d); set_child(x, y, !d); if( y == root ) root = x; pushup(y); } void splay(node *x, node *rt) { pushdown(x); while( x->fa != rt ) { node *y = x->fa; if( y->fa == rt ) rotate(x); else { if( (y->fa->ch[1] == y) == (y->ch[1] == x) ) rotate(y); else rotate(x); rotate(x); } } pushup(x); } void debug(node *x) { if( x == NIL ) return ; pushdown(x); debug(x->ch[0]); printf("%d : %d %d %d | %d %d\n", x-pl, x->ch[0]-pl, x->ch[1]-pl, x->fa-pl, x->num, x->key); debug(x->ch[1]); } int dist(node *x, node *y) { if( x == y ) return 0; splay(x, NIL), splay(y, root); if( x->ch[0] == y ) { int d = min(min(x->key, y->key), x->ch[0]->ch[1]->mn); return x->key + y->key - 2*d; } else { int d = min(min(x->key, y->key), x->ch[1]->ch[0]->mn); return x->key + y->key - 2*d; } } node *query(node *x, int d) { pushdown(x); if( x->ch[1]->mn <= d && d <= x->ch[1]->mx ) return query(x->ch[1], d); else if( x->key == d ) { splay(x, NIL); return x; } else return query(x->ch[0], d); } node *prev(node *x, node *rt) { splay(x, rt); node *ret = x->ch[0]; while( ret->ch[1] != NIL ) ret = ret->ch[1]; splay(ret, rt); return ret; } node *next(node *x, node *rt) { splay(x, rt); node *ret = x->ch[1]; while( ret->ch[0] != NIL ) ret = ret->ch[0]; splay(ret, rt); return ret; } }T; Splay::node *fir[MAXN + 5], *bac[MAXN + 5]; int n, m, root; vector<int>G[MAXN + 5]; void addedge(int u, int v) { G[u].push_back(v); } int dep[MAXN + 5], dfn[2*MAXN + 5], dcnt; void newnode(Splay::node *nw, int x, int k) { nw->ch[0] = nw->ch[1] = nw->fa = T.NIL; nw->num = x, nw->key = nw->mn = nw->mx = k, nw->tg = 0; } void dfs(int x) { dfn[++dcnt] = x, fir[x] = bac[x] = &T.pl[dcnt], newnode(&T.pl[dcnt], x, dep[x]); for(int i=0;i<G[x].size();i++) { int p = G[x][i]; dep[p] = dep[x] + 1, dfs(p); dfn[++dcnt] = x, bac[x] = &T.pl[dcnt], newnode(&T.pl[dcnt], x, dep[x]); } } Splay::node *build(int l, int r) { if( l > r ) return T.NIL; int mid = (l + r) >> 1; Splay::node *p = &T.pl[mid]; p->ch[0] = build(l, mid - 1); if( p->ch[0] != T.NIL ) p->ch[0]->fa = p; p->ch[1] = build(mid + 1, r); if( p->ch[1] != T.NIL ) p->ch[1]->fa = p; T.pushup(p); return p; } bool tag[MAXN + 5]; int main() { scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) { int l; scanf("%d", &l); for(int j=1;j<=l;j++) { int x; scanf("%d", &x); addedge(i, x); tag[x] = true; } } for(int i=1;i<=n;i++) if( !tag[i] ) root = i; newnode(&T.pl[++dcnt], 0, -1), dfs(root), newnode(&T.pl[++dcnt], 0, -1); T.root = build(1, dcnt); for(int i=1;i<=m;i++) { int op; scanf("%d", &op); if( op == 1 ) { int v, u; scanf("%d%d", &v, &u); printf("%d\n", T.dist(fir[v], fir[u])); } else if( op == 2 ) { int v, h; scanf("%d%d", &v, &h); T.splay(fir[v], T.NIL); Splay::node *u = T.query(fir[v]->ch[0], fir[v]->key-h); Splay::node *l = T.prev(fir[v], T.NIL), *r = T.next(bac[v], T.root); if( bac[l->num] == r ) bac[l->num] = l; T.set_child(l, r->ch[1], 1); Splay::node *p = r->ch[0]; newnode(r, u->num, u->key), r->ch[0] = p; r->tg += 1-h, T.pushdown(r), T.pushup(r); T.next(bac[u->num], T.NIL), T.splay(bac[u->num], T.root); bac[u->num] = r; T.set_child(T.root->ch[0], r, 1); } else if( op == 3 ) { int k; scanf("%d", &k); printf("%d\n", T.query(T.root, k)->num); } } }

## @details@ ##

一开始建树的时候没有 pushup，陷入了奇怪的 RE。。。  
之后发现，用指针邻接表的形式存储会改变儿子之间的顺序，于是改成了 vector。。。

然后就是注意 splay 查找的复杂度是均摊在 splay 操作里的，所以查找到某一个值就赶紧把它 splay 上去，不然可能会 T。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11332896.html