zrj2012-B3-0019

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：先给你一个图，让你求最小生成树，每个点有一个权值。接下来会有若干询问，每次给出点对(x,y)，找出从x到y的路径，拿出路径上所有点的权值，构成一个序列{ci},求max(ck-cj,0) (k>j)
最小生成树就不说了，说一下第二问。第二问主要是一个树形DP。首先我们来分析一下这个序列。如果我们把一个序列分成两部分，那么答案有3中可能：1、答案在前半部分序列中出现；2、答案在后半部分序列中出现；3、答案是后半部分的最大值减去前半部分的最小值。
而如果我们要找到这个序列，必须要先找到x、y的lca，老规矩，预处理每个点的第2^k^个祖先。我们发现，找寻lca的过程，实际上是把序列由部分整合为整体的过程。因此我们在记录每个点第2^k^个祖先的同时，维护从这个点到第2^k^个祖先的序列中的最大值、最小值以及max(ck-cj) (k>j，且ck,cj在序列中），然后就可以很快的知道答案了。
PS：由于序列是有方向的（x->lca->y），因此x->lca是向上的，lca->y是向下的，因此我们同时需要维护max(ck-cj) (k<j，且ck,cj在序列中）。

题目大意：先给你一个图，让你求最小生成树，每个点有一个权值。接下来会有若干询问，每次给出点对(x,y)，找出从x到y的路径，拿出路径上所有点的权值，构成一个序列{ci},求max(ck-cj,0) (k>j)

最小生成树就不说了，说一下第二问。第二问主要是一个树形DP。首先我们来分析一下这个序列。如果我们把一个序列分成两部分，那么答案有3中可能：1、答案在前半部分序列中出现；2、答案在后半部分序列中出现；3、答案是后半部分的最大值减去前半部分的最小值。

而如果我们要找到这个序列，必须要先找到x、y的lca，老规矩，预处理每个点的第2^k个祖先。我们发现，找寻lca的过程，实际上是把序列由部分整合为整体的过程。因此我们在记录每个点第2^k个祖先的同时，维护从这个点到第2^k个祖先的序列中的最大值、最小值以及max(ck-cj) (k>j，且ck,cj在序列中），然后就可以很快的知道答案了。

PS：由于序列是有方向的（x->lca->y），因此x->lca是向上的，lca->y是向下的，因此我们同时需要维护max(ck-cj) (k