题目大意

  在一颗树中，询问给定区间内所有点对的最大距离。

解题思路

  该题主要利用了一个性质：如果一个集合内距离最大的点对为，另一个集合内距离最大的点对为那么这两个集合合并后，距离最大的点对一定在a,b,c,d这四个点中。这样相当于我们知道了如何合并子问题，接下来就是解决区间查询的问题了。用线段树或者RMQ都没问题。

代码实现

在合并两个子问题时需要查询两点之间的距离：
用树上前缀和加lca就可以解决。在本问题中求lca使用了ST表的方式，复杂度 。
具体细节请参考代码：

#include <bits/stdc++.h>
#define debug(x) cerr << #x << "=" << x << endl
using namespace std;
const int MAXN = 3e5 + 5;
const int MAXM = MAXN << 1;
int head[MAXN], to[MAXM], nxt[MAXM], val[MAXM], sze, n, q;
inline void AddEdge(int u, int v, int w) {
    nxt[++sze] = head[u]; to[head[u] = sze] = v; val[sze] = w; 
} 

int lst[MAXN << 1], in[MAXN << 1], dep[MAXN], timer;
long long sum[MAXN];
inline void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    lst[++timer] = u; in[u] = timer; 
    for (int e = head[u]; e; e = nxt[e]) {
        if (to[e] == fa) continue;
        sum[to[e]] = sum[u] + val[e];
        dfs(to[e], u);
        lst[++timer] = u;
    } 
}

int st[MAXN << 1][30], lg2[MAXN << 1];
inline int dmin(int x, int y) {
    return dep[x] < dep[y] ? x : y;
}
void init() {
    for (int i = 1; i <= timer; i++) st[i][0] = lst[i];
    for (int i = 2; i <= timer; i++) lg2[i] = lg2[i / 2] + 1; 
    for (int j = 1; (1 << j) <= timer; j++) 
        for (int i = 1; i + (1 << j) - 1 <= timer; i++) 
            st[i][j] = dmin(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int findlca(int x, int y) {
    if (in[x] > in[y]) swap(x, y);
    int l = lg2[in[y] - in[x] + 1];
    return dmin(st[in[x]][l], st[in[y] - (1 << l) + 1][l]);
}
// tuple 存放的是点对， 查询两点之间的距离
inline long long querys(tuple<int, int> t) {
    return sum[get<0>(t)] + sum[get<1>(t)] - 2 * sum[findlca(get<0>(t), get<1>(t))];
}

tuple<int, int> st2[MAXN][30];
// 合并两个子问题的答案
tuple<int, int> merge(tuple<int, int>& x, tuple<int, int>& y) {
    tuple<int, int> ans = (querys(x) > querys(y) ? x : y);
    ans = (querys(ans) > querys(make_tuple(get<0>(x), get<0>(y))) ? ans : make_tuple(get<0>(x), get<0>(y)));
    ans = (querys(ans) > querys(make_tuple(get<0>(x), get<1>(y))) ? ans : make_tuple(get<0>(x), get<1>(y)));
    ans = (querys(ans) > querys(make_tuple(get<1>(x), get<0>(y))) ? ans : make_tuple(get<1>(x), get<0>(y)));
    ans = (querys(ans) > querys(make_tuple(get<1>(x), get<1>(y))) ? ans : make_tuple(get<1>(x), get<1>(y)));
    return ans; 
}
void init2() {
    for (int i = 1; i <= n; i++) st2[i][0] = make_tuple(i, i);
    for (int j = 1; (1 << j) <= n; j++) 
        for (int i = 1; i + (1 << j) - 1 <= n; i++) 
            st2[i][j] = merge(st2[i][j - 1], st2[i + (1 << j - 1)][j - 1]);
}
inline long long query(int l, int r) {
    int t = lg2[r - l + 1];
    return querys(merge(st2[l][t], st2[r - (1 << t) + 1][t]));
}
int main() {
    scanf("%d%d", &n, &q);
    for (int u, v, w, i = 1; i < n; i++) {
        scanf("%d%d%d", &u, &v, &w);
        AddEdge(u, v, w); AddEdge(v, u, w);
    }
    dfs(1, 0);
    init(); // 求lca的ST表的初始化
    init2(); // 求答案的ST表的初始化
    while (q--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%lld\n", query(l, r));
    }
    return 0;
}