P9584 题解
liangjindong0504
·
·
题解
题目传送门
好不容易在赛时写出来了，特此纪念。（小号）
这题的大数据是真的有用。
换根 dp 模板题。
【前言】
前置知识：换根 dp。
建议先行完成换根 dp 模板题以后再来做本题。
话说普及组为什么会有换根 dp？
【具体思路】
看完题，立马能想到全源最短路。可是即使用 spfa 迪杰斯特拉算法、Johnson 算法都会超时。毕竟这个 n \le 2 \times 10^5 连 O(n^2) 都过不去。（也许能得 50 分）。
既然求最短路的算法不行，该考虑玄学优化从题目限制中找线索了。
注意到题目中的一句话：
这 n 个城市之间由 n-1 条双向道路互相连接。保证从任意一个城市出发，都能通过这 n-1 条双向道路，到达任意一个城市。
树上的“全源最短路”怎么求呢？立马想到换根 dp，时间复杂度仅为 $O(n)$。
由于这是一颗无根树，因此默认根为 $1$。
换根 dp 的思路在前面的模板题的题解里面，可以看看，这里就只讲一点。
以下没有图，大家自行脑部，推荐画出来。
设 $dp_i$ 为编号是 $i$ 的点到其它点的路径长度总和，$ds_i$ 为根节点到编号为 $i$ 的节点的路径长度。
首先，有一棵树，我们可以通过 $O(n)$ 的时间求出（即遍历一遍树）编号为 $1$。
此时，$dp_1$ 已经被求出来了，即为 $\sum\limits_{i=1}^{n} ds_i$。
至于换根 dp，又是什么呢？
比如说，节点 $u$ 有一个子节点 $v$，则将根转移到 $v$ 时（其实就是统计这个子节点到各个节点路径长度总和），以 $v$ 为根的子树到根节点的距离减少了 $cost(u,v)$，其它节点到根节点的距离就增加了 $cost(u,v)$。
再预处理出 $size_i$ 为以 $1$ 号节点为根时 $i$ 节点为根的子树有几个节点。
易得状态转移方程为：$dp_v=dp_u-size_v \times cost(u,v)+size_u \times cost(u,v)$。
以此类推，直到推完所有节点。
经过换根 dp 之后，我们可以将各个节点到其它节点路径长度总和求出。
这样，预处理就结束了。
而对于每一个问题，节点 $n+1$ 到其它节点的路径之和易得出是 $dp_{k_i}+w_in$。可以看成从节点 $n+1$ 走到节点 $k_i$ ，再走到各个点。
至于其它点到节点 $n+1$ 呢？其实也是上面那个式子，因为现在节点数量为 $n+1$，边为 $n$，图还是连通图，因此现在的图还是一棵树。
因此，对于每一次询问，都可以得出结果为 $\sum\limits_{i=1}^{n} dp_i+2 \times (dp_{k_i}+w_in)$。
若还是不太懂，看看具体是如何实现的。
**【具体实现】**
第一步：输入&建图。
这一步没什么好说的，用链式前向星或者 ```vector``` 都可以建图（个人喜欢用 ```vector```）。**注意建双向边。**
```cpp
n=read();
q=read();
for(int i=1;i<n;i++){
int u,v,w;
u=read();
v=read();
w=read();
vec[u].push_back((node){v,w});
vec[v].push_back((node){u,w});
}
```
本人用了快读快输。
第二步：换根 dp（二次扫描法）。
首先是处理 $size$ 数组以及处理 $ds$ 数组，具体见代码。
```cpp
void dfs(int u){
si[u]=1;//大小当然初始化为 1（根节点）
for(int i=0;i<vec[u].size();i++){//枚举每一个子节点
//获取这条边的数据。
int z=vec[u][i].zhong;
int c=vec[u][i].chang;
//如果访问过了打断
if(flag[z]){
continue;
}
//标记一下
flag[z]=1;
//更新数组
ds[z]=ds[u]+c;
//搜索子节点
dfs(z);
//处理 size
si[u]+=si[z];
}
}
```
然后是第二次遍历，大体思路前面已经讲过了，给出的代码主要是细节实现。
```cpp
void dfn(int u){
for(int i=0;i<vec[u].size();i++){//枚举每个子结点
//获取子节点数据
int z=vec[u][i].zhong;
int c=vec[u][i].chang;
//访问过了就不访问了
if(flag[z]){
continue;
}
//标记
flag[z]=1;
//转移
dp[z]=dp[u]-si[z]*c+(n-si[z])*c;
//搜索子节点
dfn(z);
}
}
```
第三步：统计答案。
答案比较好统计，上面已经给出。只要注意**取模**就可以了。
**【最后总结】**
[完整代码](https://www.luogu.com.cn/paste/9roxml1g)。
[提交记录](https://www.luogu.com.cn/record/122958797)。
本题虽然涉及到提高组算法，但是其难度并不算太高。不过这种题目在 ```CSP-J``` 中出现的概率应该很小。可以说，这题算是 ```S``` 组 ```T1``` 的题，是为提高组选手准备的。（以上仅个人观点）
如果还有不懂的可以私信我。