- 分享
- 2017-11-10 07:56:29 @
#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 条评论
目前还没有评论...