题意：
傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。
整个地图是一个树结构，一共有 \(n\) 块空地，这些空地被 \(n-1\) 条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。
在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。如果补给站在点 \(u\) 上，并且空地 \(v\) 上有 \(d_v\) 个单位的军队，那么幽香每天就要花费 \(d_v \times \text{dist}(u,v)\) 的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为 \(\sum (d_v \times \text{dist}(u,v))\)（其中 \(1 \leq v \leq N\)）的代价，\(\text{dist}(u,v)\) 表示 \(u\) 和 \(v\) 在树上的距离（唯一路径的权和）。
因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动他的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？
你可以假定一开始所有空地上都没有军队。
分析：
以补给点 \(rt\) 为根的代价为 \(\sum_{i=1}^{n} siz_{i} \times (siz_{rt} - siz_{i}) \times w_{i}\)，其中 \(siz_{i}=\sum_{v \in subtree(i)}a_{v}\)，\(w_{i}\) 表示 \(i\) 的父亲到 \(i\) 的边权。
可以发现当 \(rt\) 为整棵树的带权重心时最优，证明如下：
考虑从补给点从 \(y\) 移动到 \(y\) 的父亲 \(x\)，对代价带来的影响。显然有：
\[\Delta = siz_{y} \times w_{y} - (siz_{rt} - siz_{y}) \times w_{y} \]考虑 \(rt\) 的一个儿子 \(son\)，根据重心的性质 \(2siz_{son} \le siz_{rt}\)。那么总有 \(2siz_{y} \le siz_{rt}\)。
因此往补给点往 \(rt\) 移动不会更劣。
如何动态维护带权重心的位置呢？
选 \(1\) 为根。那么 \(x\) 为重心的一个必要条件为 \(2(siz_{1}-siz_{x}) \le siz_{1}\)，即 \(2siz_{x} \ge siz_{1}\)。
假如 \(x\) 满足这个条件，不难发现最后重心的位置一定是在 \(x\) 子树内。
因此可以归纳出：满足 \(2siz_{x} \ge siz_{1}\) 的深度最深的 \(x\) 一定为重心。
又因为满足条件的 \(x\) 肯定是 \(1\) 所在重链的一段前缀，所以深度具有单调性。线段树二分即可。
现在的问题是：已知补给点的位置 \(x\)，计算它的代价。
套路地拆开这个式子（\(dis_{i}\) 表示根到 \(i\) 的路径边权和）：
\[\begin{aligned} ans &=\sum_{i=1}^{n}a_{i} \times \text{dist}(i,x)\\ &=\sum_{i=1}^{n}a_{i} \times (dis_{i}+dis_{x}-2\times dis_{\text{lca}(i,x)} \\ &=\sum_{i=1}^{n}a_{i} \times dis_{i} + dis_{x} \times \sum_{i=1}^{n}a_{i}-2\times \sum_{i=1}^{n} a_{i} \times dis_{\text{lca}(i,x)} \end{aligned} \]对于 \(\sum_{i=1}^{n} a_{i} \times dis_{\text{lca}(i,x)}\)。
将 a[x] += y 时，把 \(x\) 到根节点的路径上的 \(siz_{i}\) 都加上 \(y\)。
那么 \(\sum_{i=1}^{n} a_{i} \times dis_{\text{lca}(i,x)}\) 就等于 \(\sum_{i \in (1 \rightarrow x)} siz_{i} \times w_{i}\)。
树链剖分即可，时间复杂度 \(O(n+ Q \log^2 n)\)。
代码：
#include<bits/stdc++.h>
#define N 100005
#define int long long
using namespace std;
int n, Q, Siz1;
struct edge {
int to, w;
};
vector<edge>p[N];
int dis[N], P[N], P2[N], top[N], son[N], dfn[N], siz[N], father[N], id[N], tot;
int S[N * 4], W[N * 4], sum[N * 4], tag[N * 4];
void dfs1(int x, int fa) {
father[x] = fa;
siz[x] = 1;
int Maxson = -1;
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i].to;
if(y == fa) continue;
dis[y] = dis[x] + p[x][i].w;
P[y] = p[x][i].w;
dfs1(y, x);
siz[x] += siz[y];
if(siz[y] > Maxson) {
Maxson = siz[y];
son[x] = y;
}
}
}
void dfs2(int x, int topf) {
top[x] = topf;
dfn[x] = ++tot;
P2[tot] = P[x];
id[tot] = x;
if(!son[x]) return;
dfs2(son[x], topf);
for(int i = 0; i < p[x].size(); i++) {
int y = p[x][i].to;
if(top[y]) continue;
dfs2(y, y);
}
}
void pushup(int u) {
W[u] = W[u * 2] + W[u * 2 + 1];
sum[u] = sum[u * 2] + sum[u * 2 + 1];
S[u] = max(S[u * 2], S[u * 2 + 1]);
}
void build(int u, int L, int R) {
if(L == R) {
W[u] = P2[L];
return;
}
int mid = (L + R) / 2;
build(u * 2, L, mid);
build(u * 2 + 1, mid + 1, R);
pushup(u);
}
void maketag(int u, int s) {
S[u] += s;
sum[u] += W[u] * s;
tag[u] += s;
}
void pushdown(int u) {
maketag(u * 2, tag[u]);
maketag(u * 2 + 1, tag[u]);
tag[u] = 0;
}
void update(int u, int L, int R, int l, int r, int s) {
if(R < l || r < L) return;
if(l <= L && R <= r) {
maketag(u, s);
return;
}
pushdown(u);
int mid = (L + R) / 2;
update(u * 2, L, mid, l, r, s);
update(u * 2 + 1, mid + 1, R, l, r, s);
pushup(u);
}
int query_s(int u, int L, int R, int l, int r) {
if(R < l || r < L) return 0;
if(l <= L && R <= r) return sum[u];
pushdown(u);
int mid = (L + R) / 2;
return query_s(u * 2, L, mid, l, r) + query_s(u * 2 + 1, mid + 1, R, l, r);
}
void Add_Tree(int x, int s) { //[x->1]这条路径加上s
while(x) {
update(1, 1, n, dfn[top[x]], dfn[x], s);
x = father[top[x]];
}
}
int Ask_Tree(int x) {
int res = 0;
while(x) {
res += query_s(1, 1, n, dfn[top[x]], dfn[x]);
x = father[top[x]];
}
return res;
}
int query(int u, int L, int R, int x) {
if(L == R) return S[u];
pushdown(u);
int mid = (L + R) / 2;
if(x <= mid) return query(u * 2, L, mid, x);
else return query(u * 2 + 1, mid + 1, R, x);
}
int Find(int u, int L, int R) {
if(L == R) return id[L];
pushdown(u);
int mid = (L + R) / 2;
if(2 * S[u * 2 + 1] >= Siz1) return Find(u * 2 + 1, mid + 1, R);
else return Find(u * 2, L, mid);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> Q;
for(int i = 1, u, v, w; i <= n - 1; i++) {
cin >> u >> v >> w;
p[u].push_back((edge){v, w});
p[v].push_back((edge){u, w});
}
dfs1(1, 0); dfs2(1, 1);
build(1, 1, n);
int sum1 = 0, sum2 = 0, sum3 = 0, Sa = 0;
while(Q--) {
int X, v;
cin >> X >> v;
Add_Tree(X, v);
Siz1 = query(1, 1, n, dfn[1]);
int x = Find(1, 1, n); //重心
sum1 += dis[X] * v;
Sa += v;
sum2 = dis[x] * Sa;
sum3 = 2 * Ask_Tree(x);
cout << sum1 + sum2 - sum3 << endl;
}
return 0;
}