這題 FlashHu 的優化思路值得借鑒
前置引理
- 樹中所有點到某個點的距離和中,到重心的距離和是最小的。
- 把兩棵樹通過某一點相連得到一顆新的樹,新的樹的重心必然在連接配接原來兩棵樹重心的路徑上。
- 一棵樹添加或者删除一個節點,樹的重心最多隻移動一條邊的位置。
- 一棵樹最多有兩個重心,且相鄰;同時,擁有奇數個節點的樹隻有一個重心
- 其實是樹的重心本身的定義:各個子樹大小皆不超過總節點數的一半的節點即為樹的重心(證明:不管向哪一側移動,對應的子樹節點個數都是 $\le$ 樹的總節點一半的,也就是說,剩下的節點數 $\ge$ 總節點數的一半,故該點為中心)
題解
根據引理 $1$ ,題目很明顯是要求維護樹的重心
最簡單的方法是啟發式合并,根據引理 $3, 5$ ,每加一條邊,若目前子樹大小 $\ge$ 總節點數的一半,就将重心往這裡移一次,複雜度 $O (n \log^2 n)$
對于優化,根據引理 $2$ ,取出兩棵原樹在新樹上之間的路徑,進行類似二分的操作,對于目前查詢區間 $[L, p), (p, R]$ ,并同時存儲 $L$ 之前的子樹節點總和 $lsum$ ,以及 $R$ 之後的 $rsum$ ,且因為 $Splay$ 上是根據中序周遊,是以目前節點在 $Splay$ 上的左右子節點可以代表分割的左右區間,故若 $lsum + size[son[p][0]] \le half \&\& size[son[p][1]] + rsum \ge half$ ,那麼點 $p$ 即為樹的一個重心(注意由于在目前 $Splay$ 上 $lsum$ 所屬的節點屬于實點且已經跳過,故 $size[son[p][0]]$ 不會重複計算到 $lsum$,因為 $LCT$ 中維護的子樹為 $Splay$ 中的子樹,虛樹的維護是一定不會将同一 $Splay$ 的實點加進去的),根據引理 $4$ ,若總節點數為奇數,那麼已經可以結束查找了;反之則需繼續查找是否有編号更小的,看左右區間哪邊子節點多就去哪裡就好了,總複雜度 $O (n \log n)$
代碼
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4
5 using namespace std;
6
7 const int MAXN = 1e05 + 10;
8
9 int father[MAXN]= {0};
10 int son[MAXN][2]= {0};
11 int subtree[MAXN]= {0}, virsize[MAXN]= {0};
12 int revtag[MAXN]= {0};
13
14 int isroot (int p) {
15 return son[father[p]][0] != p && son[father[p]][1] != p;
16 }
17 int sonbel (int p) {
18 return son[father[p]][1] == p;
19 }
20 void reverse (int p) {
21 if (! p)
22 return ;
23 swap (son[p][0], son[p][1]);
24 revtag[p] ^= 1;
25 }
26 void pushup (int p) {
27 subtree[p] = subtree[son[p][0]] + subtree[son[p][1]] + virsize[p] + 1;
28 }
29 void pushdown (int p) {
30 if (revtag[p]) {
31 reverse (son[p][0]), reverse (son[p][1]);
32 revtag[p] = 0;
33 }
34 }
35 void rotate (int p) {
36 int fa = father[p], anc = father[fa];
37 int s = sonbel (p);
38 son[fa][s] = son[p][s ^ 1];
39 if (son[fa][s])
40 father[son[fa][s]] = fa;
41 if (! isroot (fa))
42 son[anc][sonbel (fa)] = p;
43 father[p] = anc;
44 son[p][s ^ 1] = fa, father[fa] = p;
45 pushup (fa), pushup (p);
46 }
47 int Stack[MAXN];
48 int top = 0;
49 void splay (int p) {
50 top = 0, Stack[++ top] = p;
51 for (int nd = p; ! isroot (nd); nd = father[nd])
52 Stack[++ top] = father[nd];
53 while (top > 0)
54 pushdown (Stack[top]), top --;
55 for (int fa = father[p]; ! isroot (p); rotate (p), fa = father[p])
56 if (! isroot (fa))
57 sonbel (p) == sonbel (fa) ? rotate (fa) : rotate (p);
58 }
59 void Access (int p) {
60 for (int tp = 0; p; tp = p, p = father[p])
61 splay (p), virsize[p] += subtree[son[p][1]] - subtree[tp], son[p][1] = tp, pushup (p);
62 }
63 void Makeroot (int p) {
64 Access (p), splay (p), reverse (p);
65 }
66 void Split (int x, int y) {
67 Makeroot (x);
68 Access (y), splay (y);
69 }
70 void link (int x, int y) {
71 Split (x, y);
72 father[x] = y, virsize[y] += subtree[x];
73 pushup (y);
74 }
75
76 int ances[MAXN]; // 重心用并查集維護
77 int find (int p) {
78 return p == ances[p] ? p : ances[p] = find (ances[p]);
79 }
80
81 int N, Q;
82 char opt[5];
83
84 int Newgrvy (int p) {
85 int half = subtree[p] >> 1;
86 int isodd = subtree[p] & 1;
87 int lsum = 0, rsum = 0;
88 int grvy = N + 1;
89 while (p) {
90 pushdown (p);
91 int l = lsum + subtree[son[p][0]], r = rsum + subtree[son[p][1]];
92 if (l <= half && r <= half) {
93 if (p < grvy)
94 grvy = p;
95 if (isodd)
96 return grvy;
97 }
98 if (l > r) {
99 rsum += subtree[son[p][1]] + virsize[p] + 1;
100 p = son[p][0];
101 }
102 else {
103 lsum += subtree[son[p][0]] + virsize[p] + 1;
104 p = son[p][1];
105 }
106 }
107 splay (grvy);
108 return grvy;
109 }
110
111 int getnum () {
112 int num = 0;
113 char ch = getchar ();
114
115 while (! isdigit (ch))
116 ch = getchar ();
117 while (isdigit (ch))
118 num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
119
120 return num;
121 }
122
123 int ans = 0;
124 int main () {
125 N = getnum (), Q = getnum ();
126 for (int i = 1; i <= N; i ++)
127 subtree[i] = 1, ances[i] = i, ans ^= i;
128 for (int i = 1; i <= Q; i ++) {
129 scanf ("%s", opt + 1);
130 if (opt[1] == 'A') {
131 int x = getnum (), y = getnum ();
132 link (x, y);
133 int fx = find (x), fy = find (y);
134 Split (fx, fy);
135 int grvy = Newgrvy (fy);
136 ans ^= fx ^ fy ^ grvy;
137 ances[fx] = ances[fy] = ances[grvy] = grvy;
138 }
139 else if (opt[1] == 'Q') {
140 int p = getnum ();
141 printf ("%d\n", find (p));
142 }
143 else if (opt[1] == 'X')
144 printf ("%d\n", ans);
145 }
146
147 return 0;
148 }
149
150 /*
151 10 10
152 Xor
153 Q 1
154 A 10 1
155 A 1 4
156 Q 4
157 Q 10
158 A 7 6
159 Xor
160 Q 7
161 Xor
162 */
轉載于:https://www.cnblogs.com/Colythme/p/10193202.html