CTime_Pup_314

不能再颓废了

0%

[LUOGU4299]首都

发表于 更新于 分类于 阅读次数： Valine：

题面描述

动态维护树的重心

题解

树的重心就是满足以重心为根时子节点所在最大子树最小的点

树的重心的性质

  • 树的重心为根是子节点所在最大子树大小不超过整体的一半
  • 树的所有点到重心的简单路径和最小
  • 两个联通块合并时，新的树的重心必定在原来两个联通块树的重心的简单路径上

简单证明一下 对于性质 \(1\)，假如说树的重心所在子树大小超过一半，那么除去这个子树剩下的部分大小小于一半，所以一定可以向这个子树方向上调整使最大的子树大小减小

对于性质 \(2\)，考虑最优决策点为 \(x\)，所有到 \(x\) 的简单路径长度之和为 \(f\)，则与它相邻的节点 \(y\) 到其的长度之和为 \(f+S-2size_y\)那么 \(x\) 比周围节点优的条件为 \(S-2size_y\ge0\) 即 \(size_y\le\frac{1}{2}S\)，满足重心的性质

对于性质 \(3\)，在连线上的点的最大子树一定是重心方向上，假设不在重心方向，那么原来两个子树重心就不合法了，可以向该点调整，对于不在子树上的点，它的最大子树，方向在连线上，如果不在，那么原来没有前者优

这道题关键在于如何处理这条树链，我们单独把这个树链抽出来，在对应 \(splay\) 上二分，求出每个节点向两个方向的最大子树，每次向更大子树移动即可

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e5+5;
int n, q;
int c[N][2], fa[N], s[N], si[N], rev[N];
bool nroot(int x) { return c[fa[x]][0] == x||c[fa[x]][1]  == x; }
void pushup(int x) { if(x) s[x] = s[c[x][0]]+s[c[x][1]]+si[x]+1; }
void pushr(int x) { if(x) rev[x] ^= 1, swap(c[x][0], c[x][1]); }
void pushdown(int x) { if(rev[x]) pushr(c[x][0]), pushr(c[x][1]), rev[x] = 0; }
void pushall(int x) { if(nroot(x)) pushall(fa[x]); pushdown(x); }
void rotate(int x)
{
    int y = fa[x], z = fa[y], k = c[y][1] == x, w = c[x][!k];
    if(nroot(y)) c[z][c[z][1] == y] = x; c[x][!k] = y; c[y][k] = w;
    if(w) fa[w] = y; fa[y] = x; fa[x] = z; 
    pushup(y);
}
void splay(int x)
{
    pushall(x);
    while(nroot(x))
    {
        int y = fa[x], z = fa[y];
        if(nroot(y)) rotate(c[y][1] == x^c[z][1] == y?x:y);
        rotate(x);
    }
    pushup(x);
}
void access(int x)
{
    for(int y = 0; x; x = fa[y = x])
        splay(x), si[x] += s[c[x][1]], si[x] -= s[c[x][1] = y], pushup(x);
}
void makeroot(int x) { access(x); splay(x); pushr(x); }
void split(int x, int y) { makeroot(x); access(y); splay(y);  }
void link(int x, int y)
{
    split(x, y);
    si[fa[x] = y] += s[x];
    pushup(y);
}
int f[N];
int find(int x) { return x == f[x]?x:f[x] = find(f[x]); }
int update(int x)
{
    int is_odd, hal, sil, sir, p;
    is_odd = s[x]&1, hal = s[x]>>1, sil = sir = 0, p = n+1;
    while(x)
    {
        pushdown(x);
        int sl = sil+s[c[x][0]], sr = sir+s[c[x][1]];
        if(sl <= hal&&sr <= hal&&(is_odd||p > x)) p = x;
        if(sl < sr) sil = sl+si[x]+1, x = c[x][1]; 
        else sir = sr+si[x]+1, x = c[x][0];
    }
    splay(p); 
    return p;
}
int ans;
int main()
{
    n = read(), q = read();
    for(int x = 1; x <= n; ++x) f[x] = x, s[x] = 1, ans ^= x; 
    while(q--)
    {
        char op[7]; int x, y, z; scanf("%s", op);
        if(op[0] == 'A')  
        {
            x = read(), y = read(); 
            link(x, y); split(x = find(x), y = find(y)); z = update(y);
            ans ^= x^y^z; f[x] = f[y] = f[z] = z;
        }
        else if(op[0] == 'Q') x = read(), printf("%d\n", find(x));
        else printf("%d\n", ans);
    }
    return 0;
}