手工艺品网站建设的选题背景杭州优化外包

题目大意

有一棵有$n$个节点的树，每条边有一个边权$w$。有$m$个特殊点，将这些点记为集合$A$。

将$A$中的元素随机打乱得到序列$a$，求$\sum _{i=2}^{m}d(a_{i-1},a_i)$的期望值模$998244353$后的值，其中$d(x,y)$表示$x$到$y$的边权和。

有$q$次修改，每次修改会将与$x$相连的边的权值增加$k$。求每次修改后上述式子的期望值。

$1\le n\le 5\times 10^5,m\le n,1\le q\le 5\times 10^5$

$1\le w,k\le 10^9$

题解

对于每组特殊点$x,y$，我们考虑有多少种方案会计算到$d(x,y)$的贡献。在确定$x,y$在$a$中相邻之后，其他$m-2$个数有$(m-2)!$种放法，$x,y$中较前的数可以放在第一个到第$m-1$个位置上，确定了前一个数，则后一个数也确定了，而这两个数的顺序可以为$x,y$或者$y,x$，所以还要乘$2$，也就是说有$2(m-2)!\times (m-1)=2(m-1)!$种方案会计算到$d(x,y)$的贡献。而题目要求的是期望值，总共有$m!$种方案，那么$d(x,y)$对答案的贡献为$\frac{2(m-1)!}{m!}\times d(x,y)=\frac{2}{m}\times d(x,y)$。

下面，我们要求每条边被多少$d(x,y)$计算过，这用一个$dfs$即可算出，记这个值为$t{d}_i$。然后，求出所有边$i$的$w_i$与$t{d}_i$之积的和，也就是$\sum _i{w}_i\times t{d}_i$，$\frac{m}{2}\times \sum _i{w}_i\times t{d}_i$即为答案。

我们考虑每次修改对答案的贡献。设与$i$相连的边的$td$值之和为$t{w}_i$，则每次修改会让$\sum _i{w}_i\times t{d}_i$增加$k\times t{w}_i$。那么，我们可以$O(1)$修改。因为题目只需要求答案，所以我们不需要真的去修改$w_i$。

时间复杂度为$O(n+q)$。

code

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
const long long mod=998244353;
int n,m,q,z[N+5],siz[N+5];
long long ans,pt,w[N+5],td[N+5],tw[N+5];
vector<pair<int,int>>g[N+5];
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void dfs(int u,int fa){siz[u]=z[u];for(auto p:g[u]){int v=p.first,id=p.second;if(v==fa) continue;dfs(v,u);siz[u]+=siz[v];td[id]=1ll*(m-siz[v])*siz[v]%mod;}
}
int main()
{
//	freopen("sakuya.in","r",stdin);
//	freopen("sakuya.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1,x,y;i<n;i++){scanf("%d%d%lld",&x,&y,&w[i]);g[x].push_back({y,i});g[y].push_back({x,i});}for(int i=1,x;i<=m;i++){scanf("%d",&x);z[x]=1;}dfs(1,0);for(int i=1;i<n;i++){ans=(ans+td[i]*w[i])%mod;}for(int i=1;i<=n;i++){for(auto p:g[i]){tw[i]=(tw[i]+td[p.second])%mod;}}scanf("%d",&q);long long tq=mi(m,mod-2)*2%mod;for(int o=1,x,k;o<=q;o++){scanf("%d%d",&x,&k);ans=(ans+tw[x]*k)%mod;pt=ans*tq%mod;printf("%lld\n",pt);}return 0;
}