搜索结果
查询Tags标签: 树剖,共有 4条记录-
P3250 [HNOI2016] 网络 (树剖+堆)
本题有插入路径和删除路径,在每个节点维护插入堆和删除堆,查询时两者top一样则一直弹出。如果每个节点维护的是经过他的路径,显然有些不好处理,正难则反,每个点维护不经过他的路径,那么x节点出了故障时,我们就查询x,查询到的就是x出故障后不受影响的路径。 (洛谷…
2022/7/15 23:23:40 人评论 次浏览 -
SP4155
题解里貌似没有树链剖分的写法?那蒟蒻来一发。 题目给定 \(n\) 个开始时不连通的点,每个点有点权,要求满足三个操作。判断两个输入的节点之间是否连通,如果不连通则在两点之间连边。 单点修改。 输出两个输入的节点之间路径长度。因为题目没有强制在线,所以可以尝试使…
2022/2/26 23:26:51 人评论 次浏览 -
HDU 5293 Tree chain problem (树形dp + 树剖 + LCA)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5293 \(sum[u]\) 表示子树 \(dp\) 值的和,\(dp[u]\) 表示子树 \(u\) 的答案,这里我用 \(dp[u][0]\) 表示 \(sum\), \(dp[u][1]\) 表示 \(dp\) 值。考虑以 \(u\) 结点为 \(lca\) 的链,如果不放这条链,答案就是子…
2021/7/15 6:06:27 人评论 次浏览 -
HDU 5293 Tree chain problem (树形dp + 树剖 + LCA)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5293 \(sum[u]\) 表示子树 \(dp\) 值的和,\(dp[u]\) 表示子树 \(u\) 的答案,这里我用 \(dp[u][0]\) 表示 \(sum\), \(dp[u][1]\) 表示 \(dp\) 值。考虑以 \(u\) 结点为 \(lca\) 的链,如果不放这条链,答案就是子…
2021/7/15 6:06:27 人评论 次浏览