BZOJ 3510 - 首都「 $LCT$ 动态维护树的重心」

这题 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)$

代码

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int MAXN = 1e05 + ;

 int father[MAXN]= {};

 int son[MAXN][]= {};

 int subtree[MAXN]= {}, virsize[MAXN]= {};

 int revtag[MAXN]= {};

 int isroot (int p) {

     return son[father[p]][] != p && son[father[p]][] != p;

 }

 int sonbel (int p) {

     return son[father[p]][] == p;

 }

 void reverse (int p) {

     if (! p)

         return ;

     swap (son[p][], son[p][]);

     revtag[p] ^= ;

 }

 void pushup (int p) {

     subtree[p] = subtree[son[p][]] + subtree[son[p][]] + virsize[p] + ;

 }

 void pushdown (int p) {

     if (revtag[p]) {

         reverse (son[p][]), reverse (son[p][]);

         revtag[p] = ;

     }

 }

 void rotate (int p) {

     int fa = father[p], anc = father[fa];

     int s = sonbel (p);

     son[fa][s] = son[p][s ^ ];

     if (son[fa][s])

         father[son[fa][s]] = fa;

     if (! isroot (fa))

         son[anc][sonbel (fa)] = p;

     father[p] = anc;

     son[p][s ^ ] = fa, father[fa] = p;

     pushup (fa), pushup (p);

 }

 int Stack[MAXN];

 int top = ;

 void splay (int p) {

     top = , Stack[++ top] = p;

     for (int nd = p; ! isroot (nd); nd = father[nd])

         Stack[++ top] = father[nd];

     while (top > )

         pushdown (Stack[top]), top --;

     for (int fa = father[p]; ! isroot (p); rotate (p), fa = father[p])

         if (! isroot (fa))

             sonbel (p) == sonbel (fa) ? rotate (fa) : rotate (p);

 }

 void Access (int p) {

     for (int tp = ; p; tp = p, p = father[p])

         splay (p), virsize[p] += subtree[son[p][]] - subtree[tp], son[p][] = tp, pushup (p);

 }

 void Makeroot (int p) {

     Access (p), splay (p), reverse (p);

 }

 void Split (int x, int y) {

     Makeroot (x);

     Access (y), splay (y);

 }

 void link (int x, int y) {

     Split (x, y);

     father[x] = y, virsize[y] += subtree[x];

     pushup (y);

 }

 int ances[MAXN]; // 重心用并查集维护

 int find (int p) {

     return p == ances[p] ? p : ances[p] = find (ances[p]);

 }

 int N, Q;

 char opt[];

 int Newgrvy (int p) {

     int half = subtree[p] >> ;

     int isodd = subtree[p] & ;

     int lsum = , rsum = ;

     int grvy = N + ;

     while (p) {

         pushdown (p);

         int l = lsum + subtree[son[p][]], r = rsum + subtree[son[p][]];

         if (l <= half && r <= half) {

             if (p < grvy)

                 grvy = p;

             if (isodd)

                 return grvy;

         }

         if (l > r) {

             rsum += subtree[son[p][]] + virsize[p] + ;

             p = son[p][];

         }

         else {

             lsum += subtree[son[p][]] + virsize[p] + ;

             p = son[p][];

         }

     }

     splay (grvy);

     return grvy;

 }

 int getnum () {

     int num = ;

     char ch = getchar ();

     while (! isdigit (ch))

         ch = getchar ();

     while (isdigit (ch))

         num = (num << ) + (num << ) + ch - '', ch = getchar ();

     return num;

 }

 int ans = ;

 int main () {

     N = getnum (), Q = getnum ();

     for (int i = ; i <= N; i ++)

         subtree[i] = , ances[i] = i, ans ^= i;

     for (int i = ; i <= Q; i ++) {

         scanf ("%s", opt + );

         if (opt[] == 'A') {

             int x = getnum (), y = getnum ();

             link (x, y);

             int fx = find (x), fy = find (y);

             Split (fx, fy);

             int grvy = Newgrvy (fy);

             ans ^= fx ^ fy ^ grvy;

             ances[fx] = ances[fy] = ances[grvy] = grvy;

         }

         else if (opt[] == 'Q') {

             int p = getnum ();

             printf ("%d\n", find (p));

         }

         else if (opt[] == 'X')

             printf ("%d\n", ans);

     }

     return ;

 }

 /*

 10 10

 Xor

 Q 1

 A 10 1

 A 1 4

 Q 4

 Q 10

 A 7 6

 Xor

 Q 7

 Xor

 */

巴特西

BZOJ 3510 - 首都「 $LCT$ 动态维护树的重心」

前置引理

题解

代码

最新文章

热门文章

巴特西

BZOJ 3510 - 首都 「 $LCT$ 动态维护树的重心」

前置引理

题解

代码

最新文章

热门文章

BZOJ 3510 - 首都「 $LCT$ 动态维护树的重心」