BST

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
#include <iostream>
using namespace std;

const int INF = 0x7fffffff;
const int MAXN = 500010;

int cnt_tree = 0, ans;

struct Node {
    int left_child, right_child, value, size, count;
} tree[MAXN];

void insert(int x, int y) {
    tree[x].size++;
    if (tree[x].value == y) {
        tree[x].count++;
        return;
    }
    if (tree[x].value > y) {
        if (tree[x].left_child != 0)
            insert(tree[x].left_child, y);
        else {
            cnt_tree++;
            tree[x].left_child = cnt_tree;
            tree[cnt_tree].count = tree[cnt_tree].size = 1;
            tree[cnt_tree].value = y;
        }
    } else {
        if (tree[x].right_child != 0)
            insert(tree[x].right_child, y);
        else {
            cnt_tree++;
            tree[x].right_child = cnt_tree;
            tree[cnt_tree].count = tree[cnt_tree].size = 1;
            tree[cnt_tree].value = y;
        }
    }
}

int get_rank(int x, int val) {
    if (x == 0) return 0;
    if (val == tree[x].value) return tree[tree[x].left_child].size;
    if (val > tree[x].value) return tree[tree[x].left_child].size + tree[x].count + get_rank(tree[x].right_child, val);
    if (val < tree[x].value) return get_rank(tree[x].left_child, val);
}

int get_num(int x, int y) {
    if (x == 0) return INF;
    if (tree[tree[x].left_child].size >= y) return get_num(tree[x].left_child, y);
    if (tree[tree[x].left_child].size + tree[x].count >= y) return tree[x].value;
    if (y > tree[tree[x].left_child].size) return get_num(tree[x].right_child, y - tree[tree[x].left_child].size - tree[x].count);
}

void get_pre(int x, int val) {
    if (x == 0) return;
    if (tree[x].value < val) {
        ans = max(ans, tree[x].value);
        get_pre(tree[x].right_child, val);
    }
    if (tree[x].value >= val) {
        get_pre(tree[x].left_child, val);
    }
}

void get_post(int x, int val) {
    if (x == 0) return;
    if (tree[x].value > val) {
        ans = min(ans, tree[x].value);
        get_post(tree[x].left_child, val);
    }
    if (tree[x].value <= val) {
        get_post(tree[x].right_child, val);
    }
}

int main() {
    int n;
    int op, x;
    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &op, &x);
        if (op == 5) {
            if (cnt_tree == 0) {
                cnt_tree++;
                tree[1].count = tree[1].size = 1;
                tree[1].value = x;
            } else
                insert(1, x);
        }
        if (op == 1)
            printf("%d\n", get_rank(1, x) + 1); // Find rank
        if (op == 2)
            printf("%d\n", get_num(1, x)); // Find x
        if (op == 3) {
            ans = -INF;
            get_pre(1, x);
            printf("%d\n", ans);
        }
        if (op == 4) {
            ans = INF;
            get_post(1, x);
            printf("%d\n", ans);
        }
    }
    return 0;
}

LCA

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
#include <algorithm>
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#include <iostream>
using namespace std;
const int MAXN = 500010;
struct edge {
    int to, next;
} e[MAXN << 1];

int head[MAXN], tot;
int depth[MAXN], fa[MAXN][22], lg[MAXN];

void add(int u, int v) {
    e[++tot].to = v;
    e[tot].next = head[u];
    head[u] = tot;
}

void dfs(int now, int fath) {
    fa[now][0] = fath;
    depth[now] = depth[fath] + 1;
    for(int i = 1; i <= lg[depth[now]]; ++i)
        fa[now][i] = fa[fa[now][i-1]][i-1];
    for(int i = head[now]; i; i = e[i].next)
        if(e[i].to != fath) dfs(e[i].to, now);
}


int LCA(int x, int y) {
    if (depth[x] < depth[y]) swap(x, y);
    while (depth[x] > depth[y])
        x = fa[x][lg[depth[x] - depth[y]] - 1];
    if (x == y) return x;
    for (int k = lg[depth[x]] - 1; k >= 0; --k) {
        if (fa[x][k] != fa[y][k]) {
            x = fa[x][k];
            y = fa[y][k];
        }
    }
    return fa[x][0];
}


int main() {
    fast
    int n, m, s;
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++) {
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    }
    dfs(s, 0);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        cout << LCA(u, v) << "\n";
    }
    return 0;
}