【泛做】LCT简单题选做

大概是重学了一遍 $\rm LCT$。然后整理一下之前做过的题?大多数都比较套路。

[SDOI2008]洞穴勘测

动态维护图的连通性。

保证任意时刻图的边数不超过 $n-1$ 条。

发现是个sb线段树分治,然后随便写个lct就过了(

[COCI 2009] OTOCI / 极地旅行社

给出一张空图

  • bridge u v:询问结点 u与结点 $v$ 是否连通。如果是则输出 no;否则输出 yes,并且在结点 $u$ 和结点 $v$ 之间连一条无向边。

  • penguins u x:将结点 $u$ 对应的权值$ w_u$ 修改为 $x$。

  • excursion u v:如果结点 $u$ 和结点 $v$ 不连通,则输出 impossible。否则输出结点 $u$ 到结点 $v$ 的路径上的点对应的权值的和。

保证两点存在至多一条路径。

发现是个弱智题,随便维护一下就可以。

[BJOI2014]大融合

给出一张空图

  • A x y :若 $x$ 和 $y$不连通则连边.
  • Q x y :询问 $a$ 和 $b$ 在边 $(x,y)$ 两端的 $(a,b)$ 点对数。

考虑实儿子和虚儿子数量分别维护。发现只有 accesslink 需要修改。于是魔改一下就做完了:

1
2
3
4
5
6
7
8
9
10
11
inline void Access(int x){
for (int qwq = 0 ; x ; x = T[qwq = x].F)
splay(x), npn[x] += size[rc] - size[qwq], rc = qwq, push_up(x) ;
}
inline void Rooten(int x){
Access(x), splay(x), reverse(x) ;
}
inline void Link(int x, int y){
Rooten(x), Access(y), splay(y) ;
T[x].F = y, npn[y] += size[x], push_up(y) ;
}//npn维护虚儿子

注意一个问题,就是查询的时候需要这样:

1
2
3
4
while(M --){
scanf("%s%d%d", O, &A, &B) ; if (O[0] == 'A') Link(A, B) ;
else Rooten(A), Access(B), splay(B), printf("%lld\n", 1LL * size[A] * (size[B] - size[A])) ;
}

而不是这样:

1
2
3
4
while(M --){
scanf("%s%d%d", O, &A, &B) ; if (O[0] == 'A') Link(A, B) ;
else Rooten(A), printf("%lld\n", 1LL * size[B] * (size[A] - size[B])) ;
}

大概可以理解成朝向的问题,就是B的size方向没更新,所以要改一下朝向。也就是i本来LCT是没有根的,make_root实际上是一个无根树转有根树的过程,但是转完之后除了和u一个splay里的点,剩下的点都不知道换根了。

嗯,我觉得这么编十分有道理。

[国家集训队]Tree II

一棵 $n$ 个点的树,每个点的初始权值为 $1$。

对于这棵树有 $q$ 个操作,每个操作为以下四种操作之一:

  • + u v c:将 $u$ 到 $v$ 的路径上的点的权值都加上自然数 $c$ ;
  • - u1 v1 u2 v2:将树中原有的边 $(u_1,v_1)$ 删除,加入一条新边 $(u_2,v_2)$,保证操作完之后仍然是一棵树 ;
  • * u v c:将 $u$ 到 $v$ 的路径上的点的权值都乘上自然数 $c$ ;
  • / u v:询问 $u$ 到 $v$ 的路径上的点的权值和,将答案对 $51061$ 取模。

发现就是很板的 $\rm LCT$ ?splay维护一下加法和乘法 tag 就好了。

主要是记录一下代码…

好久之前做的题了,当时给函数瞎起了一个 split 的名字,并且码风奇差,感觉自己很弟弟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
char O[3] ;
struct LCT{
bool R ; long long tagv, tags ;
int F, Son[2], sz ; long long s, v ;
}T[MAXN] ; int stk[MAXN], base[MAXN], N, M, A, B, C, i ;

inline int Find(int x) ;
inline void splay(int x) ;
inline void update(int x) ;
inline void push_down(int x) ;
inline void Mul(int x, long long y) ;
inline void Add(int x, long long y) ;
inline void reverse(int x) { lc ^= rc ^= lc ^= rc, T[x].R ^= 1 ;}

inline bool check(int x) { return T[T[x].F].Son[0] == x || T[T[x].F].Son[1] == x ; }
inline void Access(int x) { for (register int qwq = 0 ; x ; x = T[qwq = x].F) splay(x), rc = qwq, update(x) ; }
inline void Add(int x, long long y) { (T[x].s += y * size) %= Mod, (T[x].v += y) %= Mod, (T[x].tags += y) %= Mod ; }
inline void update(int x) { T[x].s = (T[lc].s + T[rc].s + T[x].v) % Mod ; T[x].sz = T[lc].sz + T[rc].sz + 1 ;}
inline void Mul(int x, long long y) { (T[x].s *= y) %= Mod, (T[x].v *= y) %= Mod, (T[x].tagv *= y) %= Mod ; (T[x].tags *= y) %= Mod ; }
inline void rotate(int x){
register int fa = T[x].F, g_fa = T[fa].F, W = x == T[fa].Son[1] ;
if (check(fa)) T[g_fa].Son[T[g_fa].Son[1] == fa] = x ; T[x].F = g_fa ;
T[fa].Son[W] = T[x].Son[W ^ 1], T[T[x].Son[W ^ 1]].F = fa, T[fa].F = x, T[x].Son[W ^ 1] = fa, update(fa), update(x) ;
}
inline void splay(int x){
register int qwq = x, t = 1 ; stk[1] = x ;
while(check(qwq)) stk[++ t] = (qwq = T[qwq].F) ;
while(t) push_down(stk[t --]) ;
while(check(x)){
register int fa = T[x].F, g_fa = T[fa].F ;
if (check(fa)) rotate((T[g_fa].Son[1] == fa) == (T[fa].Son[1] == x) ? fa : x) ; rotate(x) ;
}
}
inline int qr(){
register int res = 0, k = 1 ; char c = getchar() ;
while (!isdigit(c)) { if (c == '-') k = -1 ; c = getchar() ;}
while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
return res * k ;
}
inline void Rooten(int x) { Access(x), splay(x), reverse(x) ; }
inline void split(int x, int y) { Rooten(x), Access(y), splay(y) ; }
inline void Link(int x, int y){ Rooten(x) ; T[x].F = y ;}
inline void Cut(int x, int y){ split(x, y) ; T[x].F = T[y].Son[0] = 0 ;}
inline void push_down(int x) {
if (T[x].tagv != 1) Mul(lc, T[x].tagv), Mul(rc, T[x].tagv), T[x].tagv = 1 ;
if (T[x].tags) Add(lc, T[x].tags), Add(rc, T[x].tags), T[x].tags = 0 ;
if (T[x].R) { T[x].R = 0 ; if (lc) reverse(lc) ; if (rc) reverse(rc) ;}
}
signed main(){
cin >> N >> M ;
rep(i, 1, N) T[i].v = T[i].tagv = T[i].sz = 1 ;
rep(i ,1, N - 1) A = qr(), B = qr(), Link(A, B) ;
rep(i, 1, M){
scanf("%s", &O) ;
if (O[0] == '+') A = qr(), B = qr(), C = qr(), split(A, B), Add(B, C) ;
else if (O[0] == '*') A = qr(), B = qr(), C = qr(), split(A, B), Mul(B, C) ;
else if (O[0] == '/') A = qr(), B = qr(), split(A, B), printf("%lld\n", T[B].s) ;
else if (O[0] == '-') A = qr(), B = qr(), Cut(A, B), A = qr(), B = qr(), Link(A, B) ;
}
return 0 ;
}