主席树+树上边差分

#include<cstdio>
#include<algorithm>

using namespace std;

inline int read(){
    int x = 0;
    bool fl = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')   fl = 0;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + ch - '0';
        ch = getchar();
    }
    return fl ? x : -x;
}

const int N = 100005;
int n, u, v, p, q, maxx, k;
int val[N], fa[N][33], dep[N];

struct Edge{
    int nxt, to, dis;
}edge[N<<1];
int head[N], edge_num;
void add_edge(int from, int to, int dis){
    edge[++edge_num].nxt = head[from];
    edge[edge_num].to = to;
    edge[edge_num].dis = dis;
    head[from] = edge_num;
}
//------------------------------------------------Ö÷ϯÊ÷---
struct Seg_tree{
    int l, r, ls, rs, sum;
}tr[2000005];
int cnt, root[N];
void pushup(int cur){
    tr[cur].sum = tr[tr[cur].ls].sum + tr[tr[cur].rs].sum;
}
void build(int cur, int l, int r){
    tr[cur].l = l, tr[cur].r = r;
    if(l == r)  return;
    int mid = (l + r) >> 1;
    tr[cur].ls = ++cnt;
    tr[cur].rs = ++cnt;
    build(tr[cur].ls, l, mid);
    build(tr[cur].rs, mid+1, r);
    pushup(cur);
}
void add(int cur, int copy, int l, int r, int val){
    tr[cur] = tr[copy];
    if(l == r){
        tr[cur].sum++;
        return;
    }
    int mid = (l + r) >> 1;
    if(val <= mid){
        tr[cur].ls = ++cnt;
        add(tr[cur].ls, tr[copy].ls, l, mid, val);
    }
    else{
        tr[cur].rs = ++cnt;
        add(tr[cur].rs, tr[copy].rs, mid+1, r, val);
    }
    pushup(cur);
}
int query(int u, int v, int lca, int l, int r, int k){
    if(l == r)  return l;
    int lsize = tr[tr[u].ls].sum + tr[tr[v].ls].sum - 2 * tr[tr[lca].ls].sum;
    int mid = (l + r) >> 1;
    if(k <= lsize)  return query(tr[u].ls, tr[v].ls, tr[lca].ls, l, mid, k);
    else    return query(tr[u].rs, tr[v].rs, tr[lca].rs, mid+1, r, k - lsize);
}
void dfs_build(int x, int f){
    root[x] = ++cnt;
    add(root[x], root[fa[x][0]], 1, maxx, val[x]);
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f) continue;
        dfs_build(edge[i].to, x);
    }
}
//------------------------------------------------Lca---
void dfs(int x, int f, int depth){
    fa[x][0] = f, dep[x] = depth;
    for(int i = head[x]; i; i = edge[i].nxt){
        if(edge[i].to == f) continue;
        val[edge[i].to] = edge[i].dis;
        maxx = max(maxx, val[edge[i].to]);
        dfs(edge[i].to, x, depth + 1);
    }
}
void init(){
    for(int j = 1; (1 << j) <= n; j++)
        for(int i = 1; i <= n; i++)
            if(fa[i][j-1])
                fa[i][j] = fa[fa[i][j-1]][j-1];
}
int lca(int a, int b){
    if(dep[a] < dep[b]) a ^= b, b ^= a, a ^= b;
    int i;
    for(i = 0; (1 << i) <= dep[a]; i++); i--;
    for(int j = i; j >= 0; j--)
        if(dep[a] - (1 << j) >= dep[b])
            a = fa[a][j];
    if(a == b)  return a;
    for(int j = i; j >= 0; j--)
        if(fa[a][j] && fa[a][j] != fa[b][j]){
            a = fa[a][j];
            b = fa[b][j];
        }
    return fa[a][0];
}

int main(){
    n = read();
    for(int i = 1; i < n; i++){
        u = read(), v = read(), p = read();
        add_edge(u, v, p);
        add_edge(v, u, p);
    }
    dfs(1, 0, 1);
    init();
    build(0, 1, maxx);
    dfs_build(1, 0);
    q = read();
    while(q--){
        u = read(), v = read(), k = read();
        int Lca = lca(u, v);
        printf("%d\n", query(root[u], root[v], root[Lca], 1, maxx, k));
    }
    return 0;
}

0 条评论

目前还没有评论...