P9584 「MXOI Round 1」城市

题目描述

小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。

F 国由 $n$ 个城市构成，这 $n$ 个城市之间由 $n-1$ 条双向道路互相连接。保证从任意一个城市出发，都能通过这 $n-1$ 条双向道路，到达任意一个城市。

当然，通过这些双向道路是要收费的。通过第 $i$ 条双向道路，需要花费 $c_i$ 元。我们称 $c_i$ 为第 $i$ 条双向道路的费用。

我们定义 $cost(x,y)$ 表示从城市 $x$ 到城市 $y$ 的简单路径上，所有经过的双向道路的费用之和。特殊地，当 $x=y$ 时，$cost(x,y)=0$。

为了促进 F 国发展，小 C 新建了一个城市 $n+1$。现在他需要再新建一条双向道路，使得城市 $n+1$ 也可以通过这 $n$ 条双向道路到达任意一个城市。

他共有 $q$ 个新建道路的方案，每个方案会给定两个参数 $k_i,w_i$；对于每一个方案，你需要求出在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和，即 $\sum _{i=1}^{n+1}\sum _{j=1}^{n+1}cost(i,j)$。

由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。

方案之间相互独立，也就是说所有方案不会影响现有的道路，这些方案不会真正被施行。

输入格式

第一行两个整数 $n,q$。

接下来 $n-1$ 行，第 $i$ 行三个整数 $u_i,v_i,c_i$，表示存在一条连接城市 $u_i$ 和城市 $v_i$ 的双向道路，其费用为 $c_i$。

接下来 $q$ 行，第 $i$ 行两个整数 $k_i,w_i$，表示一个新建道路的方案。

输出格式

共 $q$ 行，每行一个整数，第 $i$ 行的整数表示在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和对 $998244353$ 取模的结果，即 $\sum _{i=1}^{n+1}\sum _{j=1}^{n+1}cost(i,j)\mathrm{mod}998244353$。

输入输出样例 #1

输入 #1

4 2
2 1 3
3 2 2
4 2 4
1 2
2 2

输出 #1

100
88

输入输出样例 #2

输入 #2

9 5
2 3 6
6 1 4
5 2 10
2 4 1
9 1 9
2 8 3
1 2 3
7 4 8
4 9
7 3
6 1
9 7
2 1

输出 #2

1050
1054
970
1148
896

说明/提示

【样例解释 #1】

在新建一条连接城市 $1$ 和城市 $5$ 且费用为 $2$ 的双向道路后，F 国的道路如下图所示：

例如，此时 $cost(4,5)=9$，$cost(1,3)=5$。

容易求得此时 $\sum _{i=1}^{n+1}\sum _{j=1}^{n+1}cost(i,j)=100$。

【样例 #3】

见附加文件中的 city/city3.in 与 city/city3.ans。

该样例满足测试点 $4$ 的限制。

【样例 #4】

见附加文件中的 city/city4.in 与 city/city4.ans。

该样例满足测试点 $11$ 的限制。

【样例 #5】

见附加文件中的 city/city5.in 与 city/city5.ans。

该样例满足测试点 $14$ 的限制。

【样例 #6】

见附加文件中的 city/city6.in 与 city/city6.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

对于 $100\%$ 的数据，$2\le n\le 2\times 10^5$，$1\le q\le 2\times 10^5$，$1\le u_i,v_i,k_i\le n$，$1\le c_i,w_i\le 10^6$，保证从任意一个城市出发，都能通过原本存在的 $n-1$ 条双向道路，到达任意一个城市。

测试点编号	$n\le$	$q\le$	特殊性质
$1\sim 3$	$80$	$80$	无
$4\sim 7$	$5000$	$5000$	无
$8\sim 10$	$5000$	$2\times 10^5$	无
$11\sim 13$	$2\times 10^5$	$2\times 10^5$	A
$14\sim 16$	$2\times 10^5$	$2\times 10^5$	B
$17\sim 20$	$2\times 10^5$	$2\times 10^5$	无

特殊性质 A：保证对于所有的 $1\le i<n$，都有 $u_i=i,v_i=i+1$。

特殊性质 B：保证对于所有的 $1\le i\le q$，都有 $k_i=1$。

C++实现

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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容