题解 P6813 【「MCOI-02」Glass 玻璃】

· · 题解

暴力推式子!

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

钦定一个根后:

首先考虑一条路径,

\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的贡献

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

再考虑统计答案

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

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

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

那么dp_u*(n-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;
}