P9584 「MXOI Round 1」城市题目描述小 C 是 F 国的总统尽管这个国家仅存在于网络游戏中但他确实是这个国家的总统。F 国由nnn个城市构成这nnn个城市之间由n−1n-1n−1条双向道路互相连接。保证从任意一个城市出发都能通过这n−1n-1n−1条双向道路到达任意一个城市。当然通过这些双向道路是要收费的。通过第iii条双向道路需要花费cic_ici元。我们称cic_ici为第iii条双向道路的费用。我们定义cost(x,y)cost(x,y)cost(x,y)表示从城市xxx到城市yyy的简单路径上所有经过的双向道路的费用之和。特殊地当xyxyxy时cost(x,y)0cost(x,y)0cost(x,y)0。为了促进 F 国发展小 C 新建了一个城市n1n1n1。现在他需要再新建一条双向道路使得城市n1n1n1也可以通过这nnn条双向道路到达任意一个城市。他共有qqq个新建道路的方案每个方案会给定两个参数ki,wik_i,w_iki,wi对于每一个方案你需要求出在新建一条连接城市kik_iki和城市n1n1n1且费用为wiw_iwi的双向道路后所有cost(i,j)cost(i,j)cost(i,j)之和即∑i1n1∑j1n1cost(i,j)\sum\limits_{i1}^{n1} \sum\limits_{j1}^{n1} cost(i,j)i1∑n1j1∑n1cost(i,j)。由于答案可能很大所以你只需要输出答案对998244353998244353998244353取模的结果。方案之间相互独立也就是说所有方案不会影响现有的道路这些方案不会真正被施行。输入格式第一行两个整数n,qn,qn,q。接下来n−1n-1n−1行第iii行三个整数ui,vi,ciu_i,v_i,c_iui,vi,ci表示存在一条连接城市uiu_iui和城市viv_ivi的双向道路其费用为cic_ici。接下来qqq行第iii行两个整数ki,wik_i,w_iki,wi表示一个新建道路的方案。输出格式共qqq行每行一个整数第iii行的整数表示在新建一条连接城市kik_iki和城市n1n1n1且费用为wiw_iwi的双向道路后所有cost(i,j)cost(i,j)cost(i,j)之和对998244353998244353998244353取模的结果即∑i1n1∑j1n1cost(i,j) mod 998244353\sum\limits_{i1}^{n1} \sum\limits_{j1}^{n1} cost(i,j) \bmod 998244353i1∑n1j1∑n1cost(i,j)mod998244353。输入输出样例 #1输入 #14 2 2 1 3 3 2 2 4 2 4 1 2 2 2输出 #1100 88输入输出样例 #2输入 #29 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输出 #21050 1054 970 1148 896说明/提示【样例解释 #1】在新建一条连接城市111和城市555且费用为222的双向道路后F 国的道路如下图所示例如此时cost(4,5)9cost(4,5)9cost(4,5)9cost(1,3)5cost(1,3)5cost(1,3)5。容易求得此时∑i1n1∑j1n1cost(i,j)100\sum\limits_{i1}^{n1} \sum\limits_{j1}^{n1} cost(i,j)100i1∑n1j1∑n1cost(i,j)100。【样例 #3】见附加文件中的city/city3.in与city/city3.ans。该样例满足测试点444的限制。【样例 #4】见附加文件中的city/city4.in与city/city4.ans。该样例满足测试点111111的限制。【样例 #5】见附加文件中的city/city5.in与city/city5.ans。该样例满足测试点141414的限制。【样例 #6】见附加文件中的city/city6.in与city/city6.ans。该样例满足测试点202020的限制。【数据范围】对于100%100\%100%的数据2≤n≤2×1052 \le n \le 2\times10^52≤n≤2×1051≤q≤2×1051 \le q \le 2\times10^51≤q≤2×1051≤ui,vi,ki≤n1 \le u_i,v_i,k_i \le n1≤ui,vi,ki≤n1≤ci,wi≤1061 \le c_i,w_i \le 10^61≤ci,wi≤106保证从任意一个城市出发都能通过原本存在的n−1n-1n−1条双向道路到达任意一个城市。测试点编号n≤n \len≤q≤q \leq≤特殊性质1∼31\sim31∼3808080808080无4∼74\sim74∼7500050005000500050005000无8∼108\sim108∼105000500050002×1052\times10^52×105无11∼1311\sim1311∼132×1052\times10^52×1052×1052\times10^52×105A14∼1614\sim1614∼162×1052\times10^52×1052×1052\times10^52×105B17∼2017\sim2017∼202×1052\times10^52×1052×1052\times10^52×105无特殊性质 A保证对于所有的1≤in1 \le i \lt n1≤in都有uii,vii1u_ii,v_ii1uii,vii1。特殊性质 B保证对于所有的1≤i≤q1 \le i \le q1≤i≤q都有ki1k_i1ki1。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN2e55,mod998244353;intn,q,to[N1],nxt[N1],c[N1],head[N],cnt,fa[N],siz[N];ll f[N],g[N],sf[N],sg[N],sumg;voidadd(intu,intv,intw){to[cnt]v;nxt[cnt]head[u];c[cnt]w;head[u]cnt;}voidinit(intu,intfat){siz[u]1,fa[u]fat;for(intihead[u];i;inxt[i]){intvto[i];if(vfa[u])continue;init(v,u);siz[u]siz[u]siz[v];}}voiddfs(intu){for(intihead[u];i;inxt[i]){intvto[i];if(vfa[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(sumgg[v])%mod;dfs(v);}}intmain(){ios::sync_with_stdio(0);intu,v,k,w;ll ans1,ans2,ans3;cinnq;for(inti1;in;i)cinuvw,add(u,v,w),add(v,u,w);init(1,0);dfs(1);for(inttmp0;tmpq;tmp){cinkw;ans1sf[k];ans2sumg-sg[k];ans32ll*n*w;cout(ans1ans2ans3mod)%modendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3356）用C++实现信奥题 P9584 「MXOI Round 1」城市
P9584 「MXOI Round 1」城市题目描述小 C 是 F 国的总统尽管这个国家仅存在于网络游戏中但他确实是这个国家的总统。F 国由nnn个城市构成这nnn个城市之间由n−1n-1n−1条双向道路互相连接。保证从任意一个城市出发都能通过这n−1n-1n−1条双向道路到达任意一个城市。当然通过这些双向道路是要收费的。通过第iii条双向道路需要花费cic_ici元。我们称cic_ici为第iii条双向道路的费用。我们定义cost(x,y)cost(x,y)cost(x,y)表示从城市xxx到城市yyy的简单路径上所有经过的双向道路的费用之和。特殊地当xyxyxy时cost(x,y)0cost(x,y)0cost(x,y)0。为了促进 F 国发展小 C 新建了一个城市n1n1n1。现在他需要再新建一条双向道路使得城市n1n1n1也可以通过这nnn条双向道路到达任意一个城市。他共有qqq个新建道路的方案每个方案会给定两个参数ki,wik_i,w_iki,wi对于每一个方案你需要求出在新建一条连接城市kik_iki和城市n1n1n1且费用为wiw_iwi的双向道路后所有cost(i,j)cost(i,j)cost(i,j)之和即∑i1n1∑j1n1cost(i,j)\sum\limits_{i1}^{n1} \sum\limits_{j1}^{n1} cost(i,j)i1∑n1j1∑n1cost(i,j)。由于答案可能很大所以你只需要输出答案对998244353998244353998244353取模的结果。方案之间相互独立也就是说所有方案不会影响现有的道路这些方案不会真正被施行。输入格式第一行两个整数n,qn,qn,q。接下来n−1n-1n−1行第iii行三个整数ui,vi,ciu_i,v_i,c_iui,vi,ci表示存在一条连接城市uiu_iui和城市viv_ivi的双向道路其费用为cic_ici。接下来qqq行第iii行两个整数ki,wik_i,w_iki,wi表示一个新建道路的方案。输出格式共qqq行每行一个整数第iii行的整数表示在新建一条连接城市kik_iki和城市n1n1n1且费用为wiw_iwi的双向道路后所有cost(i,j)cost(i,j)cost(i,j)之和对998244353998244353998244353取模的结果即∑i1n1∑j1n1cost(i,j) mod 998244353\sum\limits_{i1}^{n1} \sum\limits_{j1}^{n1} cost(i,j) \bmod 998244353i1∑n1j1∑n1cost(i,j)mod998244353。输入输出样例 #1输入 #14 2 2 1 3 3 2 2 4 2 4 1 2 2 2输出 #1100 88输入输出样例 #2输入 #29 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输出 #21050 1054 970 1148 896说明/提示【样例解释 #1】在新建一条连接城市111和城市555且费用为222的双向道路后F 国的道路如下图所示例如此时cost(4,5)9cost(4,5)9cost(4,5)9cost(1,3)5cost(1,3)5cost(1,3)5。容易求得此时∑i1n1∑j1n1cost(i,j)100\sum\limits_{i1}^{n1} \sum\limits_{j1}^{n1} cost(i,j)100i1∑n1j1∑n1cost(i,j)100。【样例 #3】见附加文件中的city/city3.in与city/city3.ans。该样例满足测试点444的限制。【样例 #4】见附加文件中的city/city4.in与city/city4.ans。该样例满足测试点111111的限制。【样例 #5】见附加文件中的city/city5.in与city/city5.ans。该样例满足测试点141414的限制。【样例 #6】见附加文件中的city/city6.in与city/city6.ans。该样例满足测试点202020的限制。【数据范围】对于100%100\%100%的数据2≤n≤2×1052 \le n \le 2\times10^52≤n≤2×1051≤q≤2×1051 \le q \le 2\times10^51≤q≤2×1051≤ui,vi,ki≤n1 \le u_i,v_i,k_i \le n1≤ui,vi,ki≤n1≤ci,wi≤1061 \le c_i,w_i \le 10^61≤ci,wi≤106保证从任意一个城市出发都能通过原本存在的n−1n-1n−1条双向道路到达任意一个城市。测试点编号n≤n \len≤q≤q \leq≤特殊性质1∼31\sim31∼3808080808080无4∼74\sim74∼7500050005000500050005000无8∼108\sim108∼105000500050002×1052\times10^52×105无11∼1311\sim1311∼132×1052\times10^52×1052×1052\times10^52×105A14∼1614\sim1614∼162×1052\times10^52×1052×1052\times10^52×105B17∼2017\sim2017∼202×1052\times10^52×1052×1052\times10^52×105无特殊性质 A保证对于所有的1≤in1 \le i \lt n1≤in都有uii,vii1u_ii,v_ii1uii,vii1。特殊性质 B保证对于所有的1≤i≤q1 \le i \le q1≤i≤q都有ki1k_i1ki1。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN2e55,mod998244353;intn,q,to[N1],nxt[N1],c[N1],head[N],cnt,fa[N],siz[N];ll f[N],g[N],sf[N],sg[N],sumg;voidadd(intu,intv,intw){to[cnt]v;nxt[cnt]head[u];c[cnt]w;head[u]cnt;}voidinit(intu,intfat){siz[u]1,fa[u]fat;for(intihead[u];i;inxt[i]){intvto[i];if(vfa[u])continue;init(v,u);siz[u]siz[u]siz[v];}}voiddfs(intu){for(intihead[u];i;inxt[i]){intvto[i];if(vfa[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(sumgg[v])%mod;dfs(v);}}intmain(){ios::sync_with_stdio(0);intu,v,k,w;ll ans1,ans2,ans3;cinnq;for(inti1;in;i)cinuvw,add(u,v,w),add(v,u,w);init(1,0);dfs(1);for(inttmp0;tmpq;tmp){cinkw;ans1sf[k];ans2sumg-sg[k];ans32ll*n*w;cout(ans1ans2ans3mod)%modendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
