题目链接：洛谷P2633-Count the a tree

题意：

给一棵树，每个点都有点权，然后m个询问，要求u节点到v节点这条路径上第k小的点权，强制在线。

题解：

树上建主席树，查询即为树上差分：sum[v]+sum[u]-sum[lca(u,v)]-sum[fa[lca(u,v)]]

非强制在线版本：https://www.spoj.com/problems/COT/

参考代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, m, cnt;
int a[MAXN + 10], b[MAXN + 10];
struct EDGE
{
    int v, nxt;
} edge[(MAXN + 10) << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v)
{
    edge[ecnt].v = v;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}

int tot = 0;
int Tree[MAXN + 10], sum[(MAXN + 10) << 6], ls[(MAXN + 10) << 6], rs[(MAXN + 10) << 6];
void update(int las, int val, int l, int r, int &rt)
{
    rt = ++tot;
    ls[rt] = ls[las];
    rs[rt] = rs[las];
    sum[rt] = sum[las] + 1;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    if (val <= mid)
        update(ls[las], val, l, mid, ls[rt]);
    else
        update(rs[las], val, mid + 1, r, rs[rt]);
}
int query(int u, int v, int lca, int f_lca, int l, int r, int k)
{
    int tmp = sum[ls[u]] + sum[ls[v]] - sum[ls[lca]] - sum[ls[f_lca]];
    int mid = (l + r) >> 1;
    if (l >= r)
        return b[l];
    if (k <= tmp)
        return query(ls[u], ls[v], ls[lca], ls[f_lca], l, mid, k);
    else
        return query(rs[u], rs[v], rs[lca], rs[f_lca], mid + 1, r, k - tmp);
}
int grand[MAXN + 10][25], depth[MAXN + 10];
void dfs_lca(int u, int FA, int dep)
{
    depth[u] = dep;
    grand[u][0] = FA;
    for (int i = 1; (1 << i) <= dep; i++)
        grand[u][i] = grand[grand[u][i - 1]][i - 1];
    for (int i = fir[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        if (v == FA)
            continue;
        update(Tree[u], a[v], 1, n, Tree[v]);
        dfs_lca(v, u, dep + 1);
    }
}
int LCA(int x, int y)
{
    if (x == y)
        return x;
    if (depth[x] > depth[y])
        swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (depth[x] < depth[y] && depth[x] <= depth[grand[y][i]])
            y = grand[y][i];
    if (x == y)
        return x;
    for (int i = 20; i >= 0; i--)
        if (grand[x][i] != grand[y][i])
            x = grand[x][i], y = grand[y][i];
    if (grand[x][0] == 0 && grand[y][0] == 0 && x != y)
        return -1;
    return grand[x][0];
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n);
    cnt = unique(b + 1, b + 1 + n) - (b + 1);
    for (int i = 1; i <= n; i++)
        a[i] = lower_bound(b + 1, b + 1 + cnt, a[i]) - b;

    ecnt = 0;
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    update(Tree[0], a[1], 1, n, Tree[1]);
    dfs_lca(1, 0, 1);
    int ans = 0;
    while (m--)
    {
        int u, v, k;
        scanf("%d%d%d", &u, &v, &k);
        u ^= ans;
        int lca = LCA(u, v);
        ans = query(Tree[u], Tree[v], Tree[lca], Tree[grand[lca][0]], 1, n, k);
        printf("%d\n", ans);
    }
    return 0;
}