Description：

求树上带权重心，带修改权。

$1\le n \le 100000$

Solution：

记 $sum[i]$ 表示以 $i$ 为根的子树权值和， $gather[i]$ 表示 $i$ 的子树集中到 $i$ 的权值， $tofa[i]$ 表示 $i$ 的子树集中到 $i$ 的父亲的权值，如果想求以 $i$ 为重心的值，就不断地跳 $fa$ ，并把其他子树到 $i$ 的贡献加上，因为已经算出了 $gather$ 和 $sum$ ，就用类似二次扫描与换根的方法计算，每次加上 $gather[fa[i]]-tofa[i]+(sum[fa[i]]-sum[i])*dis$ ， $dis$ 用树剖求，这样就可以计算每个点为重心时的值。发现如果最终的重心在当前根的某棵子树中，那么子树根的值应小于根的值，于是枚举根的所有子树，如果更优就去子树中找。

但是这样如果是链就被卡成 $O(n^2)$ ，于是每次不去子树中找，而是去所在点分树的子树中找，因为树去掉一个点会分裂成若干联通块，所以这样能保证不会丢掉最优的点，而总查找次数不超过 $log_2n$ ，总时间复杂度 $O(nlog^3n)$ （跳父亲+求值+求距离），但时限 $6s$ 而且跑不满啊。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

#define INF 0x3f3f3f3f

typedef long long ll;

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int size[MAXN],d[MAXN],root,s;

bool v[MAXN];

void getroot(int k,int f)

{

	size[k] = 1;d[k] = 0;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to] || e[i].to == f)continue;

		getroot(e[i].to,k);

		size[k] += size[e[i].to];

		if(size[e[i].to] > d[k])

		{

			d[k] = size[e[i].to];

		}

	}

	d[k] = max(d[k],s - d[k]);

	if(d[k] < d[root])root = k;

	return;

}

vector<pair<int,int> > g[MAXN];

#define fi first

#define se second

int anc[MAXN];

void divide(int k)

{

	v[k] = true;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		root = 0;s = size[e[i].to];

		getroot(e[i].to,0);

		anc[root] = k;

		g[k].push_back(make_pair(e[i].to,root));

		divide(root);

	}

	return;

}

int siz[MAXN],top[MAXN],fa[MAXN],dep[MAXN],son[MAXN];

void dfs1(int k,int depth)

{

	siz[k] = 1;

	dep[k] = depth;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + e[i].v);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

void dfs2(int k,int tp)

{

	top[k] = tp;

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return dep[a] < dep[b] ? a : b;

}

int dis(int a,int b){return dep[a] + dep[b] - 2 * dep[LCA(a,b)];}

ll sum[MAXN],gather[MAXN],tofa[MAXN];

void modify(int p,int x)

{

	sum[p] += x;

	for(int i = p;anc[i] != 0;i = anc[i])

	{

		int d = dis(p,anc[i]);

		sum[anc[i]] += x;

		gather[anc[i]] += (ll)x * d;

		tofa[i] += (ll)x * d;

	}

	return;

}

ll calc(int k)

{

	ll res = gather[k];

	for(int i = k;anc[i] != 0;i = anc[i])

	{

		res += gather[anc[i]] - tofa[i] + dis(anc[i],k) * (sum[anc[i]] - sum[i]);

	}

	return res;

}

ll query(int k)

{

	ll res = calc(k);

	for(int i = 0;i < g[k].size();++i)

	{

		if(calc(g[k][i].fi) < res)return query(g[k][i].se);

	}

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b,c;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d%d",&a,&b,&c);

		add(a,b,c);

	}

	int rt = root = 0;s = n;d[0] = INF;

	getroot(1,0);rt = root;

	divide(root);

	dfs1(1,0);dfs2(1,1);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&a,&b);

		modify(a,b);

		printf("%lld\n",query(rt));

	}

	return 0;

}