(color{#0066ff}{题目描述})
JOHNKRAM 最近在参加 C_SUNSHINE 举办的聚会。
C 国一共有 n 座城市，这些城市由 n−1 条无向道路连接。任意两座城市之间有且仅有一条路径。C_SUNSHINE 会在编号在 [1,n] 内的城市举办聚会。
为了整整 JOHNKRAM，C_SUNSHINE 把他丢在了城市 x，让他自己走到一座城市去参加聚会。JOHNKRAM 希望你能帮他计算，他最少要走多长的路才能到达一座正在聚会的城市？
当然，C_SUNSHINE 一共举行了 m 次聚会，所以 JOHNKRAM 也会询问你 m 次。
(color{#0066ff}{输入格式})
第一行包含一个整数 n，表示城市数量。
接下来 n - 1 行每行三个整数 u, v, d，表示一条无向道路的两个端点和长度。
接下来一行包含一个整数 m，表示询问个数。
接下来 m 行每行三个整数 l, r, x 表示一次询问。
表示本次在[l,r]（点的编号）的城市举办聚会
(color{#0066ff}{输出格式})
对于每次询问，输出一行一个整数，表示询问的答案。
(color{#0066ff}{输入样例})
3
1 2 1
1 3 1
3
2 3 1
2 3 2
3 3 2
(color{#0066ff}{输出样例})
1
0
2
(color{#0066ff}{数据范围与提示})
对于 50% 的数据，(n leq 1000)；
对于 70% 的数据，保证树是随机生成的；
对于 100% 的数据，(1 leq n, m leq 100000)，保证树的直径不超过 25000。
(color{#0066ff}{题解})
题意就是给你一棵有边权的树，m次询问
询问x到区间[l,r]内的点的最小值
动态点分治思想：建立点分树（把所有树的重心建成一棵树（每个点都会成为重心，所以共n个点，可以证明高度(leq logn)））
每个点所管辖的点就是点分树中的子树，维护一些信息就行了
对于本题
点分树的每个点维护一个动态开点的线段树
x的线段树中[l,r]代表点x到这个区间点的最小值
由于每个点管辖的不超过log个，所以在原图上倍增求距离，可以把每个点的线段树预处理出来(O(nlog^2n))
对于每个询问，在点分树上向上跳（被管辖的点）
距离分为两部分
一个是给出点到当前点的距离
一个是当前点到[l,r]的距离
前者用LCA， 后者在线段树上直接查询
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL in() {
char ch; int x = 0, f = 1;
while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
return x * f;
}
const int inf = 0x7f7f7f7f;
const int maxn = 1e5 + 10;
int n;
struct sgt {
protected:
struct node {
int l, r;
LL min;
node *ch[2];
node(int l = 0, int r = 0, LL min = inf): l(l), r(r), min(min) {
ch[0] = ch[1] = NULL;
}
void *operator new (size_t) {
static node *S = NULL, *T = NULL;
return (S == T) && (T = (S = new node[1024]) + 1024), S++;
}
void upd() {
min = inf;
if(ch[0]) min = std::min(min, ch[0]->min);
if(ch[1]) min = std::min(min, ch[1]->min);
}
};
node *root;
void add(node *&o, int l, int r, int pos, LL val) {
if(o == NULL) o = new node(l, r, inf);
if(l == r) return (void)(o->min = val);
int mid = (l + r) >> 1;
if(pos <= mid) add(o->ch[0], l, mid, pos, val);
else add(o->ch[1], mid + 1, r, pos, val);
o->upd();
}
LL query(node *o, int l, int r) {
if(o == NULL) return inf;
if(o->r < l || o->l > r) return inf;
if(l <= o->l && o->r <= r) return o->min;
return std::min(query(o->ch[0], l, r), query(o->ch[1], l, r));
}
public:
void add(int pos, int val) { add(root, 1, n, pos, val); }
LL query(int l, int r) { return query(root, l, r); }
};
struct node {
int to, dis;
node *nxt;
node(int to = 0, int dis = 0, node *nxt = NULL): to(to), dis(dis), nxt(nxt) {}
void *operator new (size_t) {
static node *S = NULL, *T = NULL;
return (S == T) && (T = (S = new node[1024]) + 1024), S++;
}
};
node *head[maxn];
int f[maxn], siz[maxn], sum, root;
int g[maxn][26], dep[maxn], fa[maxn];
LL d[maxn][26];
bool vis[maxn];
sgt t[maxn];
void add(int from, int to, int dis) {
head[from] = new node(to, dis, head[from]);
}
void getroot(int x, int fa) {
f[x] = 0, siz[x] = 1;
for(node *i = head[x]; i; i = i->nxt) {
if(i->to == fa || vis[i->to]) continue;
getroot(i->to, x);
siz[x] += siz[i->to];
f[x] = std::max(f[x], siz[i->to]);
}
f[x] = std::max(f[x], sum - siz[x]);
if(f[x] < f[root]) root = x;
}
void build(int x) {
vis[x] = true;
for(node *i = head[x]; i; i = i->nxt) {
if(vis[i->to]) continue;
root = 0, sum = siz[i->to];
getroot(i->to, x);
fa[root] = x;
build(root);
}
}
void dfs(int x, int fat) {
g[x][0] = fat;
dep[x] = dep[fat] + 1;
for(node *i = head[x]; i; i = i->nxt)
if(i->to != fat) dfs(i->to, x), d[i->to][0] = i->dis;
}
void beizeng() {
dfs(1, 0);
for(int j = 1; j <= 24; j++)
for(int i = 1; i <= n; i++) {
g[i][j] = g[g[i][j - 1]][j - 1];
d[i][j] = d[i][j - 1] + d[g[i][j - 1]][j - 1];
}
}
LL LCA(int x, int y) {
if(dep[x] < dep[y]) std::swap(x, y);
LL dis = 0;
for(int i = 24; i >= 0; i--) if(dep[g[x][i]] >= dep[y]) dis += d[x][i], x = g[x][i];
if(x == y) return dis;
for(int i = 24; i >= 0; i--)
if(g[x][i] != g[y][i]) {
dis += d[x][i] + d[y][i];
x = g[x][i], y = g[y][i];
}
return dis + d[x][0] + d[y][0];
}
void predoit() {
for(int i = 1; i <= n; i++) {
int x = i;
while(x) {
t[x].add(i, LCA(x, i));
x = fa[x];
}
}
}
void query() {
for(int m = in(); m --> 0;) {
int l = in(), r = in(), x = in();
LL ans = inf;
int y = x;
while(y) {
ans = std::min(ans, t[y].query(l, r) + LCA(x, y));
y = fa[y];
}
printf("%lld
", ans);
}
}
int main() {
n = in();
int x, y, z;
for(int i = 1; i < n; i++) {
x = in(), y = in(), z = in();
add(x, y, z), add(y, x, z);
}
f[0] = sum = n;
getroot(1, 0);
build(root);
beizeng();
predoit();
query();
return 0;
}