题目链接：https://ac.nowcoder.com/acm/contest/6885/F
题目大意：
中文题意
题目思路：
考虑一个原题：https://blog.csdn.net/qq_43857314/article/details/108108130
上面这题和该题思想一致的 不过上面是利用并查集合并了两个子树
这个的题变成了区间问题，那么就用倍增合并一下区间就好了
至于大部分的题解，应该都在上面原题上了
本题用到的结论也在上述题解上证明过，这里就不多解释了
所以这个题，就考虑用倍增维护区间的最长直径的两个端点，每次合并时考虑lca去合并即可
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
ll n,m,p;
ll d[maxn];
ll cnt = 0;
int pos[maxn],ppos = 0;
int f[maxn][23];
int lg[maxn],deep[maxn];
int s[maxn][23],t[maxn][23];
vector< pair<int,ll> >v[maxn];void dfs(int u,int fa,ll w){f[++ppos][0] = u;pos[u] = ppos;deep[u] = deep[fa] + 1;d[u] = d[fa]+w;for(auto x:v[u]){int e = x.first;if(e == fa)continue;dfs(e,u,x.second);f[++ppos][0] = u;}
}
void work(){lg[0] = -1;for(int i=1;i<=ppos;i++) lg[i] = lg[i/2]+1;for(int k=1;k<=20;k++){for(int i=1;i+(1<<k)-1<=ppos;i++){if(deep[f[i][k-1]]<deep[f[i+(1<<(k-1))][k-1]]) f[i][k] = f[i][k-1];else f[i][k] = f[i+(1<<(k-1))][k-1];}}
}
int LCA(int x,int y){x = pos[x],y = pos[y];if(x>y) swap(x,y);int len = lg[y-x+1];return deep[f[x][len]]<deep[f[y-(1<<len)+1][len]]?f[x][len]:f[y-(1<<len)+1][len];
}
ll dis(int a,int b){return d[a] + d[b] - 2*d[LCA(a,b)];
}
void cmp(int &x,int &y,ll &w,int a,int b){if(dis(a,b) > w){w = dis(a,b);x = a;y = b;}
}
void Merge(){for(int i=1;i<=n;i++) s[i][0] = t[i][0] = i;for(int k=1;k<=20;k++){for(int i=1;i+(1<<k)-1<=n;i++){ll res = 0;int a = s[i][k-1],b = t[i][k-1],c = s[i+(1<<(k-1))][k-1],d = t[i+(1<<(k-1))][k-1];cmp(s[i][k],t[i][k],res,a,b);cmp(s[i][k],t[i][k],res,a,c);cmp(s[i][k],t[i][k],res,a,d);cmp(s[i][k],t[i][k],res,b,c);cmp(s[i][k],t[i][k],res,b,d);cmp(s[i][k],t[i][k],res,c,d);}}
}
void MAX(ll &x,ll y){if(x<y) x = y;}
ll Query(int x,int y){ll len=lg[y-x+1];ll res = 0;int a = s[x][len],b = t[x][len],c = s[y-(1<<len)+1][len],d = t[y-(1<<len)+1][len];MAX(res,dis(a,b));MAX(res,dis(a,c));MAX(res,dis(a,d));MAX(res,dis(b,c));MAX(res,dis(b,d));MAX(res,dis(c,d));return res;
}
int main(){read(n);read(m);for(int i=1;i<=n-1;i++){ll x,y,w;read(x);read(y);read(w);v[x].push_back({y,w});v[y].push_back({x,w});}dfs(1,1,0);work();Merge();for(int i=1;i<=m;i++){ll x,y;read(x);read(y);printf("%lld\n",Query(x,y));}return 0;
}
/**
***/