tkdsheep-solution-0019

从 Trac 迁移的文章

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

原文章内容如下：

{{{
这题在POJ上有基本一样的原题，把这题出到比赛里是我的过错，但题目本身所考察的算法和数据结构是非常不错的，希望这题没有影响到大家做题时的心情
题目首先做一个最大生成树，得到一颗唯一的树
接下来有很多次查询，每次查询相当于在树上找了一条唯一的路径（起点是x，终点是y）,然后要在这条路径上找两个点，使得它们之间的差值尽可能大
假设这个差值是b-a，题目还要求要保证b比a离终点更近
如果仅仅是给这样一条链，我们可以用O(n)线性扫一遍即可
但这是一棵树，所以首先要找出这条路径，很明显需要一个LCA(x,y)，然后路径就是x->lca->y
那么答案就是max { dp(x,lca), dp(lca,y), max(lca,y)-min(lca,x) }, 也就是把路径分成两段
那么答案肯定是在这其中一段上(dp)， 或者取右段的最大值减去左段的最小值 
题目的数据范围很大，所以必须在求lca的同时，高效的维护这些值
学长们好像都用的是倍增的做法，我是用的离线Tarjan求的lca，然后Tarjan做并查集的时候顺带维护上面的那些值，做法跟prowindy学长差不多
具体的写法大家prowindy学长写的比较清楚了，必须完全理解Tarjan求LCA的整个过程是怎么回事才能写出正确的代码
我写的时候wa了很多次。。原因是我对Tarjan的并查集处理部分理解不够深刻
我的代码中维护了两个数组，father和root，father[i]代表i在树中的父亲节点，root[i]代表Tarjan过程中i的并查集祖先
这个祖先root[i]是随着Tarjan算法的进行再发生变化的，并查集find过程中顺带维护dp值的时候，不能用father，而应该用root来维护
再仔细想一下，就是一段一段的维护的，这个用文字难以描述清楚，可以自己画图出来看看
}}}

这题在POJ上有基本一样的原题，把这题出到比赛里是我的过错，但题目本身所考察的算法和数据结构是非常不错的，希望这题没有影响到大家做题时的心情
题目首先做一个最大生成树，得到一颗唯一的树
接下来有很多次查询，每次查询相当于在树上找了一条唯一的路径（起点是x，终点是y）,然后要在这条路径上找两个点，使得它们之间的差值尽可能大
假设这个差值是b-a，题目还要求要保证b比a离终点更近
如果仅仅是给这样一条链，我们可以用O(n)线性扫一遍即可
但这是一棵树，所以首先要找出这条路径，很明显需要一个LCA(x,y)，然后路径就是x->lca->y
那么答案就是max { dp(x,lca), dp(lca,y), max(lca,y)-min(lca,x) }, 也就是把路径分成两段
那么答案肯定是在这其中一段上(dp)， 或者取右段的最大值减去左段的最小值 
题目的数据范围很大，所以必须在求lca的同时，高效的维护这些值
学长们好像都用的是倍增的做法，我是用的离线Tarjan求的lca，然后Tarjan做并查集的时候顺带维护上面的那些值，做法跟prowindy学长差不多
具体的写法大家prowindy学长写的比较清楚了，必须完全理解Tarjan求LCA的整个过程是怎么回事才能写出正确的代码
我写的时候wa了很多次。。原因是我对Tarjan的并查集处理部分理解不够深刻
我的代码中维护了两个数组，father和root，father[i]代表i在树中的父亲节点，root[i]代表Tarjan过程中i的并查集祖先
这个祖先root[i]是随着Tarjan算法的进行再发生变化的，并查集find过程中顺带维护dp值的时候，不能用father，而应该用root来维护
再仔细想一下，就是一段一段的维护的，这个用文字难以描述清楚，可以自己画图出来看看