2020-2021:teams:farmer_john:2020.7.30
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:2020.7.30 [2020/08/07 17:02] 2sozx [题解] |
2020-2021:teams:farmer_john:2020.7.30 [2020/08/07 17:09] (当前版本) 2sozx [题解] |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 给定一片森林，$q$ 此询问，每次给出两个点 $u,v$ ，如果 $u,v$ 在一棵树内输出 $-1$ ，否则在这两棵树任取一点临时建立一条边，求连边后的直径的期望。$n,q\le 10^5$ | 给定一片森林，$q$ 此询问，每次给出两个点 $u,v$ ，如果 $u,v$ 在一棵树内输出 $-1$ ，否则在这两棵树任取一点临时建立一条边，求连边后的直径的期望。$n,q\le 10^5$ | ||
| ====题解==== | ====题解==== | ||
| - | 首先我们可以预处理出每个点在哪棵树中，其次预处理出每个点 $u$ 到这棵树叶子的最大值 $mx[u]$ ，将每棵树按照这个最大值进行排序，最后在处理出每棵树的直径长度 $len$ 。询问的时候枚举点数少的树，在另一棵树中寻找另一个点。将两棵树连接 $u,v$ 后的直径有两种情况： | + | 首先我们可以预处理出每个点在哪棵树中，其次预处理出每个点 $u$ 到这棵树叶子的最大值 $mx[u]$ ，这个可以用树形$DP$ 处理，将每棵树按照这个最大值进行排序，最后在处理出每棵树的直径长度 $len$ 。询问的时候枚举点数少的树，在另一棵树中寻找另一个点。将两棵树连接 $u,v$ 后的直径有两种情况： |
| * $mx[u]+mx[v]+1$ | * $mx[u]+mx[v]+1$ | ||
| * $\max(len[u],len[v])$ | * $\max(len[u],len[v])$ | ||
2020-2021/teams/farmer_john/2020.7.30.1596790965.txt.gz · 最后更改: 2020/08/07 17:02 由 2sozx
