Sol
作为一个刚刚学动态点分治的新手，表示这道题很难啃动。。。
既然是动态点分治，那么先建出点分树，之后暴跳父亲就是log的
这道题就是要求带权重心，可以证明，随意在点分树上从一个点出发，每次选最小答案的子重心，最后一定能找到答案。。感觉就相当于在树上二分。。。
修改就爆跳父亲# include# define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(2e5 + 10);IL ll Read(){ RG ll x = 0, z = 1; RG char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48); return x * z;}int n, fst[_], nxt[_], w[_], to[_], cnt, Q;IL void Add(RG int u, RG int v, RG int ww){ nxt[cnt] = fst[u]; to[cnt] = v; w[cnt] = ww; fst[u] = cnt++; }namespace ChainDiv{ int fa[_], size[_], top[_], deep[_], son[_], dfn[_], Index; IL void Dfs1(RG int u){ size[u] = 1; for(RG int e = fst[u]; e != -1; e = nxt[e]){ if(size[to[e]]) continue; deep[to[e]] = deep[u] + w[e]; fa[to[e]] = u; Dfs1(to[e]); size[u] += size[to[e]]; if(size[to[e]] > size[son[u]]) son[u] = to[e]; } } IL void Dfs2(RG int u, RG int Top){ top[u] = Top; dfn[u] = ++Index; if(son[u]) Dfs2(son[u], Top); for(RG int e = fst[u]; e != -1; e = nxt[e]) if(!dfn[to[e]]) Dfs2(to[e], to[e]); } IL ll Dis(RG int u, RG int v){ RG ll dis = deep[u] + deep[v]; while(top[u] ^ top[v]){ if(deep[top[u]] < deep[top[v]]) swap(u, v); u = fa[top[u]]; } if(deep[u] > deep[v]) swap(u, v); return dis - 2 * deep[u]; }}int size[_], mx[_], frt[_], vis[_], rt, sz, root, ft[_];struct Edge{ int nt, to, rt; } edge[_];ll sum[_], pres[_], alls[_];IL void _Add(RG int u, RG int v, RG int rrt){ edge[cnt] = (Edge){ft[u], v, rrt}; ft[u] = cnt++; }IL void Getroot(RG int u, RG int ff){ size[u] = 1; mx[u] = 0; for(RG int e = fst[u]; e != -1; e = nxt[e]){ if(vis[to[e]] || to[e] == ff) continue; Getroot(to[e], u); size[u] += size[to[e]]; mx[u] = max(mx[u], size[to[e]]); } mx[u] = max(mx[u], sz - size[u]); if(mx[u] < mx[rt]) rt = u;}IL void Create(RG int u, RG int ff){ frt[u] = ff; vis[u] = 1; for(RG int e = fst[u]; e != -1; e = nxt[e]){ if(vis[to[e]]) continue; rt = 0; sz = size[to[e]]; Getroot(to[e], u); _Add(u, to[e], rt); Create(rt, u); }}IL void Modify(RG int u, RG ll d){ sum[u] += d; for(RG int v = u; frt[v]; v = frt[v]){ RG ll dis = ChainDiv::Dis(u, frt[v]); sum[frt[v]] += d; pres[v] += d * dis; alls[frt[v]] += d * dis; }}IL ll Calc(RG int u){ RG ll ret = alls[u]; for(RG int v = u; frt[v]; v = frt[v]){ RG ll dis = ChainDiv::Dis(u, frt[v]); ret += dis * (sum[frt[v]] - sum[v]); ret += alls[frt[v]] - pres[v]; } return ret;}IL ll Query(RG int u){ RG ll tmp = Calc(u); for(RG int e = ft[u]; e != -1; e = edge[e].nt) if(Calc(edge[e].to) < tmp) return Query(edge[e].rt); return tmp;}int main(RG int argc, RG char* argv[]){ sz = n = Read(); Q = Read(); Fill(fst, -1); Fill(ft, -1); for(RG int i = 1, a, b, c; i < n; ++i) a = Read(), b = Read(), c = Read(), Add(a, b, c), Add(b, a, c); ChainDiv::Dfs1(1); ChainDiv::Dfs2(1, 1); mx[0] = n + 1; cnt = 0; Getroot(1, 0); root = rt; Create(rt, 0); while(Q--){ RG int u = Read(), d = Read(); Modify(u, d); printf("%lld\n", Query(root)); } return 0;}