洛谷P9584 「MXOI Round 1」城市

洛谷题目传送门

题目描述

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

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

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

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

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

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

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

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

输入格式

第一行两个整数 n,q。

接下来 n−1 行，第 i 行三个整数 ui,vi,ci，表示存在一条连接城市 ui 和城市 vi 的双向道路，其费用为 ci。

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

输出格式

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

输入输出样例

输入 #1

输出 #1

100
88

输入 #2

输出 #2

说明/提示

【样例解释 #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≤n≤200000，1≤q≤200000，1≤ui,vi,ki≤n，1≤ci,wi≤1000000，保证从任意一个城市出发，都能通过原本存在的 n−1 条双向道路，到达任意一个城市。

测试点编号	n≤	q≤	特殊性质
1∼3	80	8080	无
4∼7	5000	5000	无
8∼10	5000	200000	无
11∼13	200000	200000	A
14∼16	200000	200000	B
17∼20	200000	200000	无

特殊性质 A：保证对于所有的 1≤i<n，都有 ui=i,vi=i+1。

特殊性质 B：保证对于所有的 1≤i≤q，都有 ki=1。

附件下载

city.zip1.24MB

思路

很明显是换根dp

如图，令dp[u] 为 u 到其他所有节点的距离和

所以 dp[u]=dp[fa]-(siz[u]-1)*dis(u,fa)+(n-siz[u]-1)*dis(u,fa)

其中 fa 为 u 的父亲节点，siz[u] 为 u 及其子节点的数量和

因为 u 到每一个节点的距离相较于 fa 的距离，u 的子树都少经过了边(u,fa)(不包括 u)，除 u 及其子树与 fa 都多经过了边(u,fa)，这样我们就可以求出没有加点的所有距离和 ans

对于新加入的点，我们只需要求出这个点到其他所有点的距离y，ans+y*2即为答案

因为一个点到所以点的距离等于所以点到这个点的距离

而新加入的点到其他点的距离为这个点相邻的点到所以的点的距离加上n*wi

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=4e5+5,mod=998244353;
ll h[N],ne[N],to[N],w[N],tot,dp[N],siz[N],n,m,ans;
void add(ll u,ll v,ll d){tot++;to[tot]=v;w[tot]=d;ne[tot]=h[u];h[u]=tot;
}
void dfs1(ll u,ll fa,ll ww){//求出所有点及其子树的大小和 1 到所有点的距离 siz[u]=1;for(ll i=h[u];i;i=ne[i]){ll v=to[i];if(v==fa)continue;dfs1(v,u,ww+w[i]);siz[u]=(siz[u]+siz[v])%mod;dp[1]=(dp[1]+ww+w[i])%mod;}
}
void dfs2(ll u,ll fa){//求出所有点到其他点的距离 for(ll i=h[u];i;i=ne[i]){ll v=to[i];if(v==fa)continue;dp[v]=(dp[u]-(siz[v]-1)*w[i]%mod+(n-siz[v]-1)*w[i]%mod+mod)%mod;ans=(ans+dp[v])%mod;//求出距离和 ans dfs2(v,u);}
}
int main(){cin>>n>>m;ll x,y,z;for(ll i=1;i<n;i++){cin>>x>>y>>z;add(x,y,z);add(y,x,z);}dfs1(1,0,0);dfs2(1,0);ans=(ans+dp[1])%mod;for(ll i=1;i<=m;i++){y=0;cin>>x>>z;cout<<(ans+(dp[x]+z*n)*2%mod)%mod<<'\n';}return 0;
}