DDOSvoid's Blog

loj 6038 「雅礼集训 2017 Day5」远行

发表于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

题目描述

https://loj.ac/p/6038

简要题意：现在有 $n$ 个点，同时有 $m$ 次操作，操作有两种，第一种操作给定两个点 $x,y$，加入一条连接 $x$ 和 $y$ 的边，保证加入边之后仍然是森林；第二种操作给定一个点 $x$，问 $x$ 所在的联通块内与它距离最远的点的距离

$n\le 3\times 10^5,m\le 5\times 10^5$，强制在线

Solution

首先根据直径的性质，我们知道距离一个点最远的点一定是任意一条直径的两个端点中的某一个端点，所以我们只需要在有加边的情况下动态维护直径，同时根据直径的性质，两个两个联通块的并的直径是各自的联通块的两条直径和两对端点分别组合形成的四个路径共六个路径中的某一个，那么现在我们还需要支持动态加边，求树上两点的距离，这个东西只能用 $LCT$ 来维护，所以我们用 $LCT$ 来维护距离，用并查集维护直径即可

时间复杂度 $O(n\log n)$

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define maxn 300010
using namespace std;

#define lc T[i].ch[0]
#define rc T[i].ch[1]
struct LinkCutTree {
    int v, val, ch[2];
    bool rev; 
} T[maxn]; int f[maxn];
void init_LCT(int n) {
    for (int i = 1; i <= n; ++i) T[i].v = T[i].val = 1;
}
inline int get(int i) {
    if (T[f[i]].ch[0] == i) return 0;
    if (T[f[i]].ch[1] == i) return 1;
    return -1;
}
inline void maintain(int i) {
    T[i].v = T[i].val + T[lc].v + T[rc].v;
} 
inline void setr(int i) { 
    if (!i) return ;
    T[i].rev ^= 1; swap(lc, rc); 
}
inline void push(int i) {
    bool &rev = T[i].rev; 
    if (rev) setr(lc), setr(rc);
    rev = 0;
}
inline void rotate(int x) {
    int fa = f[x], ffa = f[f[x]], wx = get(x);
    if (~get(fa)) T[ffa].ch[T[ffa].ch[1] == fa] = x;
    f[x] = ffa; f[fa] = x; f[T[x].ch[wx ^ 1]] = fa;
    T[fa].ch[wx] = T[x].ch[wx ^ 1]; T[x].ch[wx ^ 1] = fa;
    maintain(fa); maintain(x); 
} 
void clt(int i) {
    static int st[maxn], top;
    st[top = 1] = i; 
    while (~get(i)) st[++top] = i = f[i];
    while (top) push(st[top--]); 
}
void Splay(int i) {
    clt(i);
    for (int fa = f[i]; ~get(i); rotate(i), fa = f[i])
        if (~get(fa)) rotate(get(i) == get(fa) ? fa : i);
}
void access(int i) { for (int p = 0; i; i = f[p = i]) Splay(i), rc = p, maintain(i); }
inline void make_rt(int i) { access(i); Splay(i); setr(i); }
inline void split(int x, int y) { make_rt(x); access(y); Splay(y); }
int find_rt(int i) { access(i); Splay(i); while (lc) i = lc; return Splay(i), i; }
inline void link(int x, int y) {
    //   if (find_rt(x) == find_rt(y)) return ;
    split(x, y); f[x] = y;
}
inline int D(int x, int y) { return split(x, y), T[y].v - 1; } 

struct node {
    int x, y, d;

    node(int x = 0, int y = 0, int d = 0) : x(x), y(y), d(d) {}
    friend bool operator < (const node &u, const node &v) { return u.d < v.d; } 
};

int fa[maxn]; node w[maxn];
void init_fa(int n) { for (int i = 1; i <= n; ++i) fa[i] = i, w[i] = node(i, i, 0); }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    fa[fx] = fy; 
    w[fy] = max({ w[fx], w[fy],
                node(w[fx].x, w[fy].x, D(w[fx].x, w[fy].x)),
                node(w[fx].y, w[fy].x, D(w[fx].y, w[fy].x)),
                node(w[fx].x, w[fy].y, D(w[fx].x, w[fy].y)),
                node(w[fx].y, w[fy].y, D(w[fx].y, w[fy].y)) });
}

int lans, type;
inline void solve_1() {
    int x, y; cin >> x >> y;
    x ^= lans * type, y ^= lans * type;
    link(x, y), merge(x, y);
}

inline void solve_2() {
    int x, fx; cin >> x;
    x ^= lans * type;
    fx = find(x); 
    cout << (lans = max(D(w[fx].x, x), D(w[fx].y, x))) << "\n";
}

int n, m; 

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> type >> n >> m; init_LCT(n); init_fa(n); 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    }
    return 0;
}