Jittery Roads Gym - 100889J (虚树 + DP + dfs 序, + 线段树)

每次给一个点集, 求每个点到其他所有点的最大距离:

会修改边权;   

修改边权之后,

我们可以用 dfs 序 + 线段树维护 当前点到根节点的距离.

还可以用树状数组 + 差分思想 维护. {

dfs 序之后,每个点都会有一个维护的区间,然后我们在这个区间里加上这个点保存的边权.

每个边 修改,我们修改这个区间. 区间开头 + , 结尾 - 就可以了; 

最后直接查询一下就会是点到根节点的距离.

}

然后我们建虚树的时候,可以不每次都拿 1 当根节点,可以找一个 rt .

Top_xiao的犯错记录:

写这个题的时候,出现了几个问题:
1. 建完虚树的时候, 把原图 和 虚树的图弄混了,竟然 用 par[u][0] 当做 u 的父亲.
2. 然后 跑 f2 的时候,不能用 f[it] 因为  f[it] 用可能还没有更新到.因为是同一个父亲节点,直接用 f[u] 就可以.
3. 第一次以 1 为根节点建虚树的时候, 1 有可能并不是关键点,但是会被算进来. 所以算 f2 的时候需要特判一下.
4. 然后换了一种建虚树的方法, 并不是 以 1 当做根节点. 这个时候根节点的 f2 还要是 0, 还需要特判一下. 
     但是比 上一种 特判简单.
5. 最后 我的 dis 没有更新完全, 就是只更新了关键点,那些 lca 的非关键点没有更新.tmd.

#include
#define ls now << 1
#define rs now << 1 | 1
using namespace std;
const int N = 1e5 + 100;
struct edge {int u, v, w, next;
} g[N <&l

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！