1 #include <iostream>  2 #include <cstdio>  3 #include <algorithm>  4 #include <cmath>  5 #include <cstring>  6 #include <set>  7 #include <vector>  8 #include <queue>  9 #include <map> 10 #include <list> 11 #include <bitset> 12 #include <string> 13 #include <cctype> 14 #include <cstdlib> 15  16 using namespace std; 17  18 typedef long long ll; 19 typedef unsigned long long ull; 20 #define inf (0x3f3f3f3f) 21 #define lnf (0x3f3f3f3f3f3f3f3f) 22 #define eps (1e-8) 23 int sgn(double a) { 24     return a < -eps ? -1 : a < eps ? 0 : 1; 25 } 26  27 int n, q; 28 const int maxn = 50010; 29 const int m = 100001; 30 struct Node { 31     int v, c; 32 }; 33  34 vector<Node>  g[maxn]; 35 const int DEG = 16; 36 int fa[maxn][DEG]; 37 int deg[maxn]; 38  39 void addedge(int u, int v, int w) { 40     Node a, b; 41     a.v = v; 42     a.c = w; 43     b.v = u; 44     b.c = w; 45     g[u].push_back(a); 46     g[v].push_back(b); 47 } 48  49 void bfs(int root) { 50     queue<int> q; 51     deg[root] = 0; 52     fa[root][0] = root; 53     q.push(root); 54     while(!q.empty()) { 55         int tmp = q.front(); 56         q.pop(); 57         for(int i = 1; i < DEG; i++) { 58             fa[tmp][i] = fa[fa[tmp][i - 1]][i - 1]; 59         } 60         for(int i = 0; i < (int)g[tmp].size(); i++) { 61             int v = g[tmp][i].v; 62             if(v == fa[tmp][0])continue; 63             deg[v] = deg[tmp] + 1; 64             fa[v][0] = tmp; 65             q.push(v); 66         } 67     } 68 } 69  70 int LCA(int u, int v) { 71     if(deg[u] > deg[v])swap(u, v); 72     for(int det = deg[v] - deg[u], i = 0; det; det >>= 1, i++) { 73         if(det & 1)v = fa[v][i]; 74     } 75     if(u == v)return u; 76     for(int i = DEG - 1; i >= 0; i--) { 77         if(fa[u][i] != fa[v][i]) { 78             u = fa[u][i]; 79             v = fa[v][i]; 80         } 81     } 82     return fa[u][0]; 83 } 84  85  86  87  88 int T[maxn], lson[maxn * 30], rson[maxn * 30]; 89 int c[maxn * 30]; 90 int tot = 0; 91  92 int build(int l, int r) { 93     int root = tot++; 94     c[root] = 0; 95     if(l != r) { 96         int mid = (l + r) >> 1; 97         lson[root] = build(l, mid); 98         rson[root] = build(mid + 1, r); 99     }100     return root;101 }102 103 104 int update(int root, int pos, int val) {105     int newroot = tot++, tmp = newroot;106     c[newroot] = c[root] + val;107     int l = 1, r = m;108     while(l < r) {109         int mid = (l + r) >> 1;110         if(pos <= mid) {111             lson[newroot] = tot++;112             rson[newroot] = rson[root];113             newroot = lson[newroot];114             root = lson[root];115             r = mid;116         } else {117             rson[newroot] = tot++;118             lson[newroot] = lson[root];119             newroot = rson[newroot];120             root = rson[root];121             l = mid + 1;122         }123         c[newroot] = c[root] + val;124     }125     return tmp;126 }127 128 int query(int u_root, int v_root, int fa_root, int k) {129     int l = 1, r = m;130     while(l < r) {131         int mid = (l + r) >> 1;132         if(c[lson[u_root]] + c[lson[v_root]] - 2 * c[lson[fa_root]] >= k) {133             r = mid;134             u_root = lson[u_root];135             v_root = lson[v_root];136             fa_root = lson[fa_root];137         } else {138             l = mid + 1;139             k -= c[lson[u_root]] + c[lson[v_root]] - 2 * c[lson[fa_root]];140             u_root = rson[u_root];141             v_root = rson[v_root];142             fa_root = rson[fa_root];143         }144     }145     return l;146 }147 148 149 150 void dfs(int u, int par, int val) {151     T[u] = update(T[par], val, 1);152     for(int i = 0; i < (int)g[u].size(); i++) {153         int v = g[u][i].v;154         if(v == par)continue;155         dfs(v, u, g[u][i].c);156     }157 }158 159 160 void init() {161     for(int i = 1; i <= n; i++) {162         g[i].clear();163     }164     tot = 0;165     memset(fa, 0, sizeof(fa));166 }167 168 void solve() {169     while(~scanf("%d%d", &n, &q)) {170         init();171         for(int i = 0; i < n - 1; i++) {172             int u, v, w;173             scanf("%d%d%d", &u, &v, &w);174             w++;175             addedge(u, v, w);176 177         }178         bfs(1);179         T[0] = build(1, m);180         dfs(1, 0, 1);181         while(q--) {182             int u, v;183             scanf("%d%d", &u, &v);184             int fa = LCA(u, v);185             int k = (c[T[u]] + c[T[v]] - 2 * c[T[fa]] + 1) / 2;186             printf("%d\n", query(T[u], T[v], T[fa], k) - 1);187         }188 189     }190 191 }192 193 194 195 int main() {196 197 #ifndef ONLINE_JUDGE198 //    freopen("1.in", "r", stdin);199     //freopen("1.out", "w", stdout);200 #endif201     //iostream::sync_with_stdio(false);202     solve();203     return 0;204 }