自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 22:49:51，当前版本为作者最后更新于2023-08-04 18:30:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Task 1~3

每次暴力求解答案即可。

Task 4~7

对于每个询问，我们考虑每条边对答案的贡献。

我们设某条边 $i$ 的一侧有 $p_i$ 个点，由于总点数是 $n+1$，所以这条边的另一侧就有 $n+1-p_i$ 个点。

那么这条边被经过的次数就是 $p_i \times (n+1-p_i) \times 2$，这条边的贡献就是 $p_i \times (n+1-p_i) \times 2 \times c_i$。

接下来我们思考如何 $O(1)$ 求每条边的贡献。

我们首先假定 $1$ 为根，对于每个点 $u$，处理出以 $u$ 为根的子树的大小 $siz_u$。

那么我们假设对于某条边 $i$，它连接的两个节点为 $u$ 和 $v$，其中 $u$ 是 $v$ 的父亲。

若新加入的点 $n+1$ 在以 $v$ 为根的子树内，则 $p_i=siz_v+1$，贡献就是 $(siz_v+1) \times (n-siz_v) \times 2 \times c_i$；

若新加入的点 $n+1$ 在以 $v$ 为根的子树外，则 $p_i=siz_v$，贡献就是 $siz_v \times (n+1-siz_v) \times 2 \times c_i$；

最后我们处理出每一条边的贡献，求和即为答案。单次询问的时间复杂度为 $O(n)$，总复杂度为 $O(nq)$。

Task 8~10

我们对目标式子进行一下变换：

$$\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j))+2 \times\sum\limits_{i=1}^{n} cost(i,n+1) $$

对于新建的边 $n$，根据刚才得到的结论，容易发现它的贡献一定为 $n\times 2\times w$，那么目标式子又可以进一步化简：

$$\begin{aligned} \sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) &=(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j))+2 \times\sum\limits_{i=1}^{n} cost(i,n+1)\\ &=(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j))+2 \times (\sum\limits_{i=1}^{n} cost(i,k))+n\times 2\times w \end{aligned} $$

那么我们可以 $O(n^2)$ 预处理出 $k=1\sim n$ 时 $2 \times (\sum\limits_{i=1}^{n} cost(i,k))$ 的值，每次询问用对应的 $2 \times (\sum\limits_{i=1}^{n} cost(i,k))$ 加上 $(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j))+n\times 2\times w$ 即可，时间复杂度 $O(n^2+q)$。

Task 11~13

容易发现，对于每一个询问，新建的 $n+1$ 号节点都在以 $2\sim k$ 为根的子树中。

我们假设对于某条边 $i$，它连接的两个节点为 $u$ 和 $v$，其中 $u$ 是 $v$ 的父亲，那么 $1\sim k-1$ 这些边的贡献都是 $(siz_v+1) \times (n-siz_v) \times 2 \times c_i$，$k \sim n-1$ 这些边的贡献都是 $siz_v \times (n+1-siz_v) \times 2 \times c_i$。

这个东西显然是可以前缀和预处理的，那么我们每次询问都可以利用前缀和去求这两部分的答案，最后加上 $n \times 2 \times w$ 即可，时间复杂度 $O(n+q)$。

Task 14~16

由于保证了 $k=1$，所以我们可以用 Task 8~10 的方法，预处理出 $k=1$ 对应的 $2 \times (\sum\limits_{i=1}^{n} cost(i,k))$，每次询问对其加上 $(\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} cost(i,j))+n\times 2\times w$ 即可，时间复杂度 $O(n+q)$。

Task 17~20

显然的，对于每一个询问，$1$ 号节点到 $k$ 号节点的简单路径上经过的所有点的子树中都包含新加入的 $n+1$ 号节点。

我们假设对于某条边 $i$，它连接的两个节点为 $u$ 和 $v$，其中 $u$ 是 $v$ 的父亲，那么对于每一个询问，$1$ 号节点到 $k$ 号节点的简单路径上经过的所有边的贡献都是 $(siz_v+1) \times (n-siz_v) \times 2 \times c_i$，剩余边的贡献都是 $siz_v \times (n+1-siz_v) \times 2 \times c_i$。

那我们可以对每个节点 $u$，求出 $1$ 号节点到 $u$ 号节点的简单路径上经过的所有边的 $(siz_v+1) \times (n-siz_v) \times 2 \times c_i$ 之和，储存在 $f_v$，同时也求出所有边的 $siz_v \times (n+1-siz_v) \times 2 \times c_i$ 之和，储存在 $g_v$，记录一下所有 $n-1$ 条边的 $siz_v \times (n+1-siz_v) \times 2 \times c_i$ 之和 $sum$，每次询问的答案即 $f_k+sum-g_k+n \times 2 \times w$。

预处理的复杂度为 $O(n)$，单次询问的复杂度为 $O(1)$，总复杂度 $O(n+q)$，可以通过。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5,mod=998244353;
int n,q,to[N<<1],nxt[N<<1],c[N<<1],head[N],cnt,fa[N],siz[N];
ll f[N],g[N],sf[N],sg[N],sumg;
void add(int u,int v,int w){
	to[++cnt]=v;
	nxt[cnt]=head[u];
	c[cnt]=w;
	head[u]=cnt;
}
void init(int u,int fat){
	siz[u]=1,fa[u]=fat;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		init(v,u);
		siz[u]=siz[u]+siz[v];
	}
}
void dfs(int u){
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa[u]) continue;
		f[v]=1ll*(siz[v]+1)*(n-siz[v])%mod*c[i]*2%mod;
		g[v]=1ll*siz[v]*(n-siz[v]+1)%mod*c[i]*2%mod;
		sf[v]=(f[v]+sf[u])%mod;
		sg[v]=(g[v]+sg[u])%mod;
		sumg=(sumg+g[v])%mod;
		dfs(v);
	}
}
int main(){
	ios::sync_with_stdio(0);
	int u,v,k,w;
	ll ans1,ans2,ans3;
	cin>>n>>q;
	for(int i=1;i<n;i++) cin>>u>>v>>w,add(u,v,w),add(v,u,w);
	init(1,0);
	dfs(1);
	for(int tmp=0;tmp<q;tmp++){
		cin>>k>>w;
		ans1=sf[k];
		ans2=sumg-sg[k];
		ans3=2ll*n*w;
		cout<<(ans1+ans2+ans3+mod)%mod<<endl;
	}
	return 0;
}