萌新刚学 OI，萌新刚学点分治，求调。

由于这题不敢多交，下载了测试点发现 #1 WA 了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, Q, fir[N], nxt[N << 1], son[N << 1], w[N << 1], tot = 1, pos[N], p, dep[N], LCA[N][25], lg[N], dist[N], x, y, z, Eula[N];
int root, Fir[N], Nxt[N << 1], Son[N << 1], sz[N], hs[N], maxn, rt, S, fa[N], dis[N], disfa[N], d[N], sum[N], Dis, ans, tem, val;
bool cut[N << 1];
inline void add(int x, int y, int z){
	nxt[++tot] = fir[x];
	fir[x] = tot;
	son[tot] = y;
	w[tot] = z;
}
inline void Add(int x, int y){
	Nxt[++tot] = Fir[x];
	Fir[x] = tot;
	Son[tot] = y;
}
inline void addnode(int x, int aa){
	pos[++p] = x;
	LCA[p][0] = x;
	if(aa) Eula[x] = p;
}
inline void dfs(int x, int ff){
	dep[x] = dep[ff] + 1;
	addnode(x, 1);
	for(int i = fir[x]; i ; i = nxt[i]){
		if(Eula[x] != p) addnode(x, 0);
		if(son[i] == ff) continue ;
		dist[son[i]] = dist[x] + w[i];
		dfs(son[i], x);
	}
}
inline void rmq(){
	for(int i = 2; i <= p; i++) lg[i] = lg[i >> 1] + 1;
	for(int j = 1; j <= lg[p]; j++){
		for(int i = 1; i + (1 << j) - 1 <= p; i++){
			x = LCA[i][j - 1];
			y = LCA[i + (1 << j - 1)][j - 1];
			LCA[i][j] = dep[x] < dep[y] ? x : y;
		}
	}
}
inline int lca(int x, int y){
	x = Eula[x], y = Eula[y];
	if(x > y) swap(x, y);
	int kk = lg[y - x + 1];
	x = LCA[x][kk];
	y = LCA[y - (1 << kk) + 1][kk];
	return dep[x] < dep[y] ? x : y;
}
inline int getdis(int x, int y){
	return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}
inline void get_sum(int x, int ff){
	sz[x] = 1;
	for(int i = fir[x]; i ; i = nxt[i]){
		if(son[i] == ff || cut[i]) continue ;
		get_sum(son[i], x);
		sz[x] += sz[son[i]];
	}
}
inline void get_rt(int x, int ff){
	hs[x] = 0;
	for(int i = fir[x]; i ; i = nxt[i]){
		if(son[i] == ff || cut[i]) continue ;
		get_rt(son[i], x);
		hs[x] = max(hs[x], sz[son[i]]);
	}
	hs[x] = max(hs[x], S - sz[x]);
	if(hs[x] < maxn) rt = x, maxn = hs[x];
}
inline void solve(int x, int ff){
	for(int i = fir[x]; i ; i = nxt[i]){
		if(cut[i]) continue ;
		cut[i] = cut[i ^ 1] = 1;
		get_sum(son[i], 0);
		maxn = S = sz[son[i]];
		get_rt(son[i], 0);
		Add(x, rt);
		fa[rt] = x;
		solve(rt, x);
	}
}
inline void modify(int x, int val){
	sum[x] += val;
	for(int i = x; fa[i]; i = fa[i]){
		Dis = getdis(x, fa[i]);
		dis[fa[i]] += Dis * val;
		disfa[i] += Dis * val;
		sum[fa[i]] += val;
	}
}
inline int calc(int x){
	int res = dis[x];
	for(int i = x; fa[i]; i = fa[i]){
		res += (dis[fa[i]] - disfa[i]);
		Dis = getdis(x, fa[i]);
		res += (sum[fa[i]] - sum[i]) * Dis;
	}
	return res;
}
inline int query(int x){
	ans = calc(x);
//	printf("%lld %lld\n", x, ans);
	for(int i = Fir[x]; i ; i = Nxt[i]){
		tem = calc(Son[i]);
		if(tem < ans) return query(Son[i]);
	}
	return ans;
}
signed main(){
//	freopen("tree1.in", "r", stdin);
//	freopen("tree.out", "w", stdout);
	scanf("%lld%lld", &n, &Q);
	for(int i = 1; i < n; i++){
		scanf("%lld%lld%lld", &x, &y, &z);
		add(x, y, z), add(y, x, z);
	}
	dfs(1, 0);
	rmq();
//	for(int i = 1; i <= n; i++, putchar('\n')){
//		for(int j = 1; j <= n; j++){
//			printf("%d ", lca(i, j));
//		}
//	}
	tot = 0;
	S = maxn = n;
	get_sum(1, 0);
	get_rt(1, 0);
	root = rt;
	solve(rt, 0);
	while(Q--){
		scanf("%lld%lld", &x, &val);
		modify(x, val);
		printf("%lld\n", query(root));
		printf("\n\n\n");
	}
	return 0;
}