自动搬运

查看原文

来自洛谷，原作者为

	loveJY 世皆纵横，唯我彳亍

搬运于2025-08-24 22:24:14，当前版本为作者最后更新于2020-09-20 20:16:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

暴力推式子!

第一篇题解虽然详细但是细节还是要补充的....

钦定一个根后:

首先考虑一条路径,

$$\sum_{i}^nV_i\sum_{j}^mW_j$$

然后我们分离一条边

$$\sum_{i}^nV_i * W_j$$

然后我们裂开西格玛

设1~l表示了这个边所在的下面子树的路径的点

l+1~n就表示这个边所管子树外的路径上的点

$$\sum_{j=1}^l V_j \sum_{i=l+1}^n V_i * W_k$$

嗯,再看看所有路径一起,设S为一条路径

$\sum_S *(\sum_{j=1}^l V_j \sum_{i=l+1}^n V_i * W_k[i,j \in S])$

设这条边管束的点为u,即u到fa的边是这条边

这个式子的左半部分表示子树内所有点到点u的路径点权和,可以用dp处理

$dp_{u}=\sum_{v}dp_v + siz[u]*a[u]$

右半部分表示子树外所有点到点u的路径点权和,换根DP

转移时考虑除去这个子树的贡献,并且加上其他点到到点u的贡献

$$ f[v] = dp[u] - dp[v] - siz[v] * a[u] + f[u] +(n - siz[u]) * a[u]; $$

前三项是u其他子树到v的贡献,剩下是算上u被统计几次

再考虑统计答案

你会发现直接相乘f,dp数组是不行的,因为我们是带权的....

但是冷静一下会发现我们相当于把每条路径拆成两半算

那么我们可以考虑这一半被算的次数

那么$dp_u*(n-siz[u])*w_i$就表示子树内一半的贡献

$f_u*siz[u]*w_i$表示另一半

这样我们算好了一个边的贡献

又由于乘法分配律,我们不难看出所有边这样算的贡献和就是答案了

时间复杂度$O(n)$

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e6 + 7;
const int MAXM = 4e6 + 7;
const int P = 998244353;
int n, home[MAXN], nxt[MAXM], to[MAXM], w[MAXM], ccnt, a[MAXN], siz[MAXN];
ll dp[MAXN], f[MAXN], ans;

namespace fastIO {
#define BUF_SIZE (1<<21)
	static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = BUF_SIZE + buf;
	inline char nc() {
		if(p1 == pend) {
			p1 = buf;
			pend = buf + fread(buf, 1, BUF_SIZE, stdin);
		}
		return *p1++;
	}
	inline int read() {
		char s = nc();
		int x = 0;
		for(; !isdigit(s); s = nc());
		for(; isdigit(s); s = nc())x = (x << 1) + (x << 3) + s - '0';
		return x;
	}
}
using namespace fastIO;

inline void ct(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	w[ccnt] = z;
}

inline void add(ll &x, ll y) {
	x += y;
	if(x >= P)x -= P;
}

inline void dfs1(int u, int F) {
	siz[u] = 1;
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		dfs1(v, u);
		add(dp[u], dp[v]);
		siz[u] += siz[v];
	}
	add(dp[u], 1ll * siz[u] * a[u] % P);
	return ;
}

inline void dfs2(int u, int F) {
	for(int i = home[u]; i; i = nxt[i]) {
		int v = to[i];
		if(v == F)continue;
		f[v] = ((dp[u] - dp[v]  - 1ll * siz[v] * a[u] % P + P) % P + f[u] + 1ll * (n - siz[u]) * a[u] % P) % P;
		add(f[v], P);
		add(ans, ((1ll * f[v] * siz[v] % P * w[i] % P + 1ll * w[i] * dp[v] % P * (n - siz[v]) % P) % P + P) % P);
		dfs2(v, u);
	}
	return ;
}


int main() {
	n = read();
	for(int i = 1; i <= n; ++i) {
		a[i] = read();
	}
	for(int i = 1, x, y, z; i < n; ++i) {
		x = read();
		y = read();
		z = read();
		ct(x, y, z);
		ct(y, x, z);
	}
	dfs1(1, 0);//第一遍dfs考虑做出所有点子树内到他的路径点权和
	dfs2(1, 0);//第二遍dfs考虑做出所有点子树外到他的路径点权和并计算答案
	printf("%d\n", 1ll * ans * 2 % P);
	return 0;
}