P9584 题解（2023 激励计划评分 5）

· · 题解

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;
}