题目地址：洛谷：【SP10628】COT – Count on a tree – 洛谷、SPOJ：SPOJ.com – Problem COT、BZOJ：Problem 2588. — Spoj 10628. Count on a tree

题目描述

You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:

• u v k : ask for the kth minimum weight on the path from node u to node v

给你一棵带点权的树，每次询问求u到v路径上的k小权值。

输入输出格式

输入格式：
In the first line there are two integers N and M. (N, M <= 100000)
In the second line there are N integers. The ith integer denotes the weight of the ith node.
In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).
In the next M lines, each line contains three integers u v k, which means an operation asking for the kth minimum weight on the path from node u to node v.

输出格式：
For each operation, print its result.

输入输出样例

输入样例#1：

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2 

输出样例#1：

2
8
9
105
7 

题解

这是一个主席树的题目。考虑每个点建一个权值线段树，维护从根到该点的路径权值。DFS一遍，对于一个点，从其父亲处插入该点的权值。权值需要离散化处理一下。直接钦点1为树根也行。询问的时候，查询该点LCA，查询时路径上的答案为u+v-lca-fa[lca]，考虑像区间k小值那样，四个线段树一起跑。这里我的LCA是倍增写法。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 100005;

int n, m, w[MAXN], ut, vt, kt;
std::vector<int> gra[MAXN];
int tmp[MAXN], tsiz;

// seg tree

struct Node {
    int lch, rch, val;
} tree[MAXN << 5];
int tot = 0, rt[MAXN];

inline void insert(int &o, int l, int r, int x) {
    tree[++tot] = tree[o];
    o = tot;
    tree[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tree[o].lch, l, mid, x);
    else insert(tree[o].rch, mid + 1, r, x);
}

inline int query(int lo, int ro, int fo, int ffo, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) >> 1;
    int num = tree[tree[lo].lch].val + tree[tree[ro].lch].val - tree[tree[fo].lch].val - tree[tree[ffo].lch].val;
    if(k <= num) return query(tree[lo].lch, tree[ro].lch, tree[fo].lch, tree[ffo].lch, l, mid, k);
    else return query(tree[lo].rch, tree[ro].rch, tree[fo].rch, tree[ffo].rch, mid + 1, r, k - num);
}

// lca

int l2n, dep[MAXN], anc[MAXN][20];

void dfs(int u) {
    rt[u] = rt[anc[u][0]];
    insert(rt[u], 1, tsiz, w[u]);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == anc[u][0]) {
            continue;
        }
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        dfs(v);
    }
}

inline void init() {
    for(int j = 1; (1 << j) <= n; j++) {
        for(int i = 1; i <= n; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

inline int lca(int a, int b) {
    if(dep[a] > dep[b]) std::swap(a, b);
    int del = dep[b] - dep[a];
    for(int i = 0; (1 << i) <= del; i++) {
        if((1 << i) & del) b = anc[b][i];
    }
    if(a != b) {
        for(int i = l2n; i >= 0; i--) {
            if(anc[a][i] != anc[b][i]) {
                a = anc[a][i];
                b = anc[b][i];
            }
        }
        return anc[a][0];
    } else {
        return a;
    }
}

int main() {
    n = readint();
    m = readint();
    l2n = log(n) / log(2);
    for(int i = 1; i <= n; i++) {
        tmp[i] = w[i] = readint(); 
    }
    std::sort(tmp + 1, tmp + n + 1);
    tsiz = std::unique(tmp + 1, tmp + n + 1) - tmp - 1;
    for(int i = 1; i <= n; i++) {
        w[i] = std::lower_bound(tmp + 1, tmp + tsiz + 1, w[i]) - tmp;
    }
    for(int i = 1; i <= n - 1; i++) {
        ut = readint();
        vt = readint();
        gra[ut].push_back(vt);
        gra[vt].push_back(ut);
    }
    dfs(1);
    init();
    while(m--) {
        ut = readint();
        vt = readint();
        kt = readint();
        int lcat = lca(ut, vt);
        printf("%d\n", tmp[query(rt[ut], rt[vt], rt[lcat], rt[anc[lcat][0]], 1, tsiz, kt)]);
    }
    return 0;
}