HDU 4916 Count on the path

意甲冠军：

考虑到一棵树，m询价  不要求回答每一次询价u和v通过在两个节点形成的最低等级点路径

思路：

一開始以为是LCA…  只是T了好几次…  后来发现不用LCA也可做

考虑每一个询问u和v  假设他们的lca不是1  则1一定是答案  只是求lca会T  那么我们仅仅须要在遍历树的时候给节点染色  染的颜色就是1的儿子的颜色  假设x这个点在y的子树中（y是1的儿子）那么他的颜色就是y

染完色后我们考虑答案是怎样构成的

如图所看到的  答案即是  红色  蓝色  绿色的子树中节点的最小值  那么我们仅仅须要分开三部分求解就可以

定义f[u][x]表示以u为根的子树中第x大的节点标号  这个能够通过树形dp求解  有了这个就能够解决绿色和红色的部分

定义g[u]表示u节点上面到1的路径中旁側的子树的最小节点标号  即图中蓝色部分  也能够利用f做树形dp求解

注意：

题目中不让蓝色部分包括绿色部分  也不把绿色部分放在红色部分中考虑的原因就是u和v节点中的一个可能是1

因为我写的是dfs  杭电会爆栈  所以记得加栈  并用C++提交

代码：

         
            
版权声明：本文博主原创文章，博客，未经同意不得转载。