传送门

调了两个小时，终于过了……

凭啥人家代码80行我180行啊！！！

谁叫你大括号换行

谁叫你写缺省源

思路

显然，补给点所在的位置就是这棵树的带权重心。

考虑size已知时如何找重心：一开始设答案在\(x\)，若存在\(x\)的一个子节点\(v\)，使\(size_v>sum-size_v\)，即\(2size_v>sum\)，就往\(v\)走，重复该过程，直到走不动为止。

考虑用点分树优化这一过程：由于点分树层数不超过\(\log n\)，这题又保证\(deg\leq 20\)，可以暴力往下跳。

然而由于在点分树上跳，与原树有一些区别，需要搞一些奇怪的东西。

假设点分树上\(x\)点有\(v\)点为儿子且满足上述要求，在原树上有\(x\rightarrow w\)这条边，且\(w\)在\(v\)的点分树的子树里，那么就要把除了\(v\)这个连通块以外的\(size\)加到\(w\)上。

即：\(size_w+=size_x-size_v\)，其中\(size\)表示点分树上的子树的\(\sum d\)。（不明白为什么要叫作\(d\)，叫\(val\)不好么？）

求出重心后还要把刚才的修改操作撤销。

得到重心之后就很好做了，沿点分树往上跳就好了。

需要维护以下几样东西：

设点分树上有节点\(x\)，它在点分树上的父亲是\(fa\)，它在点分树上的子树为\(S\)，则有：

记录这几样东西就可以统计答案了。

听着还好，写的时候思路很容易乱，务必要理清。

不然您就会像我一样记录了一堆东西全都没用

假设\(q,n\)同阶，则最后复杂度\(O(20n\log n)\)？反正能过就行，而且还挺快。

代码

#include<bits/stdc++.h>

namespace my_std{

	using namespace std;

	#define pii pair<int,int>

	#define fir first

	#define sec second

	#define MP make_pair

	#define rep(i,x,y) for (int i=(x);i<=(y);i++)

	#define drep(i,x,y) for (int i=(x);i>=(y);i--)

	#define go(x) for (int i=head[x];i;i=edge[i].nxt)

	#define sz 101010

	typedef long long ll;

	template<typename T>

	inline void read(T& t)

	{

		t=0;char f=0,ch=getchar();

		double d=0.1;

		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();

		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();

		if(ch=='.')

		{

			ch=getchar();

			while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();

		}

		t=(f?-t:t);

	}

	template<typename T,typename... Args>

	inline void read(T& t,Args&... args){read(t); read(args...);}

	void file()

	{

		#ifndef ONLINE_JUDGE

		freopen("a.txt","r",stdin);

		#endif

	}

	inline bool chkmin(int &x,int y){return x>y?x=y,1:0;}

	inline bool chkmax(int &x,int y){return x<y?x=y,1:0;}

//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}

}

using namespace my_std;

#define v edge[i].t

namespace T

{

	struct hh{int t;ll w;int nxt;}edge[sz<<1];

	int head[sz],ecnt;

	void make_edge(int f,int t,ll w)

	{

		edge[++ecnt]=(hh){t,w,head[f]};

		head[f]=ecnt;

		edge[++ecnt]=(hh){f,w,head[t]};

		head[t]=ecnt;

	}

	ll val[sz];

	ll Dep[sz];

	void dfs(int x,int fa){ go(x) if (v!=fa) { Dep[v]=Dep[x]+edge[i].w; dfs(v,x); } }

	bool vis[sz];

	int size[sz],sum,rt,rtS;

	void calcS(int x,int fa)

	{

		size[x]=1;

		go(x) if (v!=fa&&!vis[v]) { calcS(v,x); size[x]+=size[v]; }

	}

	void findrt(int x,int fa)

	{

		int S=sum-size[x];

		go(x) if (v!=fa&&!vis[v]) { findrt(v,x); chkmax(S,size[v]); }

		if (chkmin(rtS,S)) rt=x;

	}

	int findrt(int x){ calcS(x,0); sum=size[x]; rtS=1e9; findrt(x,0); return rt; }

}

#define goT(x) for (int i=T::head[x];i;i=T::edge[i].nxt)

#define Tv T::edge[i].t

namespace S

{

	int root;

	struct hh{int t,nxt;}edge[sz<<1];

	int head[sz],ecnt;

	void make_edge(int f,int t){edge[++ecnt]=(hh){t,head[f]};head[f]=ecnt;}

	ll sumv[sz],sumV[sz],sumFV[sz];

	int ff[sz];

	struct hhh{int u,uu;ll dis;};

	vector<hhh>in[sz];

	void calcDis(int x,int fa,int u,int uu,ll dis)

	{

		in[x].push_back((hhh){u,uu,dis});

		goT(x) if (Tv!=fa&&!T::vis[Tv]) calcDis(Tv,x,u,uu,dis+T::edge[i].w);

	}

	void build(int x)

	{

		T::vis[x]=1;

		goT(x) if (!T::vis[Tv])

		{

			int rt=T::findrt(Tv);

			make_edge(x,rt);

			calcDis(Tv,0,x,rt,T::edge[i].w);

			ff[rt]=Tv;

			build(rt);

		}

	}

	void build(){root=T::findrt(1);build(root);}

	void change(int x,ll s) // val_x+=s

	{

		T::val[x]+=s;sumv[x]+=s;

		drep(t,(int)in[x].size()-1,0)

		{

			int u=in[x][t].u,uu=in[x][t].uu;ll D=in[x][t].dis*s;

			sumv[u]+=s;sumV[u]+=D;sumFV[uu]+=D;

		}

	}

	ll getans(int x)

	{

		ll ret=sumV[x];

		drep(t,(int)in[x].size()-1,0)

		{

			int u=in[x][t].u,uu=in[x][t].uu;ll dis=in[x][t].dis;

			go(u) if (v!=uu) ret+=sumFV[v]+sumv[v]*dis;

			ret+=T::val[u]*dis;

		}

		return ret;

	}

	int getroot(int x)

	{

		go(x) if (sumv[v]*2>sumv[x])

		{

			int delta=sumv[x]-sumv[v];

			change(ff[v],delta);

			int ret=getroot(v);

			change(ff[v],-delta);

			return ret;

		}

		return x;

	}

	ll getans(){return getans(getroot(root));}

}

int n,Q;

int main()

{

	file();

	read(n,Q);

	int x,y,z;

	rep(i,1,n-1) read(x,y,z),T::make_edge(x,y,z);

	S::build();

	while (Q--)

	{

		read(x,y);

		S::change(x,y);

		printf("%lld\n",S::getans());

	}

}

（压了一下行，只剩\(151\)行了）

（反正我写这么丑也没人看QwQ）