题解：城市

题目链接

你说得对，但是不如换根。换根是由原先的树形 DP 简单变换而来，故事发生在这道叫做《城市》的题目中，在这里你妄图求解每个点到树中其它所有节点的距离，即 \(f_i = \sum_{j = 1}^n dis_{i \to j}\)。可以一次 dfs 求解出 \(f_{root}\)，然后我们发现走过一条边 \((u,v,w)\) 会使得 \(siz_v\) 个节点减少 \(w\) 的距离，\(n - siz_v\) 个点增加 \(w\) 的距离，于是你就得到了 \(f_v = f_u + w \times (n - 2 \times siz_v)\)，再做一次 dfs 即可。对于每个询问的答案显然为 \(\sum_{i = 1}^n f_i + 2 \times (f_k + n \times w)\)。这样我们代码比标程短 114514 倍，还更好想好写。同时效率上 std 跑一遍我的代码能够跑三遍，超越了绝大多数程序（包括你）的水平，这就是换根给我骄傲的资本。

namespace LgxTpre
{
    static const int MAX=200010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    
    int n,q,dis[MAX],siz[MAX],f[MAX],ans;
    int x,y,z,k,w;
    vector<pii> G[MAX];
	
    inline void lmy_forever()
    {
    	read(n,q);
    	for(int i=1;i<n;++i) read(x,y,z),G[x].eb(mp(y,z)),G[y].eb(mp(x,z));
    	
    	auto dfs1=[&](auto dfs1,int now,int father)->void
    	{
    		siz[now]=1;
    		for(auto [to,val]:G[now]) if(to!=father) dis[to]=Cadd(dis[now],val),dfs1(dfs1,to,now),siz[now]+=siz[to],Madd(f[1],dis[to]);
		};
		dfs1(dfs1,1,0);
		
		auto dfs2=[&](auto dfs2,int now,int father)->void
		{
			Madd(ans,f[now]);
			for(auto [to,val]:G[now]) if(to!=father) f[to]=Cadd(f[now],Cmul(val,((siz[1]-2*siz[to])%Mod+Mod)%Mod)),dfs2(dfs2,to,now);
		};
		dfs2(dfs2,1,0);
		
		for(int i=1;i<=q;++i) read(k,w),write(Cadd(ans,Cmul(Cadd(f[k],Cmul(n,w)),2ll)),'\n');
    }
}