BZOJ2588 Spoj 10628. Count on a tree

BZOJ2588

求树上路径上节点权值k小。

可以发现树上两点u,v之间的第k小点权等价于(root <-> u) + (root <-> v) - (root <-> lca(u, v)) - (root <-> father[lca(u, v)])上的第k小点权,其中root为根节点,lca(u, v)为u和v的最近公共祖先,father[lca(u, v)]为lca(u, v)的父节点。

那么可以维护root到所有节点的权值,显然root到某个点x的权值和root到x父节点的权值只有点x这个点权的差别,那么可以用主席树维护这个东西了。


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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cmath>


const int N = 100000 + 10, lgN = 20;


int v[N], begin[N], next[N * 2], to[N * 2], anc[N][lgN], dep[N], a[N], ls[N * lgN], rs[N * lgN], sum[N * lgN], root[N];
int totedge, upl, totnode;


void dfs(int );
int lca(int , int );
void amend(int& , int , int , int , int );
int query(int , int , int , int , int , int , int );
void add(int , int );
int read(void);


int main(void)
{
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i)
        a[i] = v[i] = read();
    std::sort(a + 1, a + n + 1);
    upl = std::unique(a + 1, a + n + 1) - a;
    for (int i = 1; i < n; ++i)
    {
        int x = read(), y = read();
        add(x, y);
        add(y, x);
    }
    dfs(dep[1] = 1);
    for (int ans = 0; m--; )
    {
        int x = read() ^ ans, y = read(), k = read(), t = lca(x, y);
        ans = a[query(root[x], root[y], root[t], root[anc[t][0]], 1, upl, k)];
        printf("%d", ans);
        if (m)
            putchar('\n');
    }
    return 0;
}


inline void add(int x, int y)
{
    to[++totedge] = y;
    next[totedge] = begin[x];
    begin[x] = totedge;
}


void dfs(int x)
{
    amend(root[x], root[anc[x][0]], 1, upl, std::lower_bound(a + 1, a + upl, v[x]) - a);
    for (int i = 1; (1 << i) <= dep[x]; ++i)
        anc[x][i] = anc[anc[x][i - 1]][i - 1];
    for (int i = begin[x]; i; i = next[i])
    {
        int y = to[i];
        if (y != anc[x][0])
        {
            anc[y][0] = x;
            dep[y] = dep[x] + 1;
            dfs(y);
        }
    }
}


void amend(int &x, int y, int l, int r, int val)
{
    x = ++totnode;
    ls[x] = ls[y];
    rs[x] = rs[y];
    sum[x] = sum[y] + 1;
    if (l < r - 1)
    {
        if (val < (l + r) / 2)
            amend(ls[x], ls[y], l, (l + r) / 2, val);
        else
            amend(rs[x], rs[y], (l + r) / 2, r, val);
    }
}


int query(int x, int y, int t, int ft, int l, int r, int k)
{
    if (l == r - 1)
        return l;
    int tmp = sum[ls[x]] + sum[ls[y]] - sum[ls[t]] - sum[ls[ft]];
    if (k <= tmp)
        return query(ls[x], ls[y], ls[t], ls[ft], l, (l + r) / 2, k);
    return query(rs[x], rs[y], rs[t], rs[ft], (l + r) / 2, r, k - tmp);
}


inline int lca(int x, int y)
{
    if (dep[x] < dep[y])
        std::swap(x, y);
    for (int i = 0; dep[x] > dep[y]; ++i)
        if ((1 << i) & (dep[x] - dep[y]))
            x = anc[x][i];
    if (x == y)
        return x;
    for (int i = log(dep[x]) / log(2) + 1; anc[x][0] != anc[y][0]; --i)
        if (anc[x][i] != anc[y][i])
        {
            x = anc[x][i];
            y = anc[y][i];
        }
    return anc[x][0];
}


inline int read(void)
{
    char x;
    while (x = getchar(), x != '-' && !isdigit(x))
        ;
    bool flag = x == '-';
    int num = (flag ? getchar() : x) - '0';
    while (isdigit(x = getchar()))
        (num *= 10) += x - '0';
    return flag ? -num : num;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注