team2012-D1-sol-0019

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 题目大意 ===
给出 n 个点, m 条边, 边有权值. 先求一个最小生成树. 然后在这个生成树上做查询: 每个点有一个值 b[i]. 每次查询给出两个端点 x 和 y, 求在树上从 x 点到 y 点这个结点序列中的 max{b[i]-b[j]|i在序列中在j的后面, 或者 i == j}.

=== 数据范围 ===
 * 1 <= n <= m <= 50000

=== 解题思路 ===
第一问求最小生成树用 prim 或者 kruskal 都行. 我是用 kruskal 的, 因为后面 tanjan 算法求 LCA 也要用到并查集.

第二问利用 tarjan 离线 LCA 算法来做树形 DP. 具体的可以参考 prowindy 学长的解题报告. 不过我没去看 prowindy 学长是如何完成查询的, 我自己是在访问完结点 x 的所有子结点, 函数要返回之前, 这时候算一下所有 LCA 是 x 的查询的 ans. 因为此时 x 是你所要查询的结点的根结点, 所以分别对起点和终点 find() 一下可以维护到 x 这段区间的值了. 思想和 tarjan 离线算法的思想差不多.

题目大意

给出 n 个点, m 条边, 边有权值. 先求一个最小生成树. 然后在这个生成树上做查询: 每个点有一个值 b[i]. 每次查询给出两个端点 x 和 y, 求在树上从 x 点到 y 点这个结点序列中的 max{b[i]-b[j]|i在序列中在j的后面, 或者 i == j}.

数据范围

• 1 <= n <= m <= 50000

解题思路

第一问求最小生成树用 prim 或者 kruskal 都行. 我是用 kruskal 的, 因为后面 tanjan 算法求 LCA 也要用到并查集.

第二问利用 tarjan 离线 LCA 算法来做树形 DP. 具体的可以参考 prowindy 学长的解题报告. 不过我没去看 prowindy 学长是如何完成查询的, 我自己是在访问完结点 x 的所有子结点, 函数要返回之前, 这时候算一下所有 LCA 是 x 的查询的 ans. 因为此时 x 是你所要查询的结点的根结点, 所以分别对起点和终点 find() 一下可以维护到 x 这段区间的值了. 思想和 tarjan 离线算法的思想差不多.