标签: 树链剖分

5 篇文章

CF GYM102759 I. Query On A Tree 17
Description 题目链接:GYM102759 I 给定一棵以 $1$​ 为根节点的拥有 $N$​ 个节点的带点权树,初始时每个点的点权均为 $0$​,有 $Q$​ 次操作,每次操作有两种类型: 1 u,以 $u$ 为根节点的子树内每个点点权均加 $1$。2 u v,将节点 $u$ 到节点 $v$ 的简单路径上的点的点权均加 $1$。 每次操…
义乌中学暑假集训 2021.07.09 D
Description 给定一棵 $n$​ 个节点的树 $T$​,有 $m$​ 个询问,每次询问给定 $l,r$​,问存在多少个 $k\in Z$​,使从树上编号为 $l$​ 的点沿着 $l\rightarrow r$​ 的简单路径走 $k$​ 步恰好到达 $k$​。 $1\leq n\leq 3\times 10^5,1\leq m\leq 3\…
LuoguP2542 [AHOI2005] 航线规划
Description 题目链接:P2542 给定一个 $n$ 个点 $m$ 条边的无向图,定义 $u,v$ 的关键边为从 $u$ 到 $v$ 的所有路径都必须经过的边,给定 $q$ 个操作: 查询 $u,v$ 两点间的关键边数量。删除边 $u,v$,保证合法。 保证任意时刻任意两点联通,不可能出现重边和自环。 $1\leq n\leq 3\tim…