[原创]SPOJ - COT Count on a tree [LCA+主席树]【数据结构】
[原创]SPOJ - COT Count on a tree [LCA+主席树]【数据结构】
2017-03-12 20:26:05 Tabris_ 阅读数:814
博客爬取于2020-06-14 22:41:18
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/61631979
题目链接:http://www.spoj.com/problems/COT/en/
——————————————————————————————————————
COT - Count on a tree
#tree
You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.
We will ask you to perform the following operation:
u v k : ask for the kth minimum weight on the path from node u to node v
Input
In the first line there are two integers N and M.(N,M<=100000)
In the second line there are N integers.The ith integer denotes the weight of the ith node.
In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).
In the next M lines,each line contains three integers u v k,which means an operation asking for the kth minimum weight on the path from node u to node v.
Output
For each operation,print its result.
Example
Input:
8 58 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2
Output:
2
8
9
105
7
Submit solution!
——————————————————————————————————————
题目大意:
就是求在树上 (u,v)的路上的第K小的权值
解题思路:
首先对于求第K小的问题 我们可以用主席树搞 ,没有问题,
但是对于一个树形结构,我们需要将其转化为线性,然后需要树剖才能做.
然后考虑链上的第k值怎么维护 ,
发现如果树剖计算的话 维护不了啊
因为(u,v)的路 可能在很多个链上,那么不能对每个求第K值,这样明显是错误的啊,
然后我们知道主席树其实就是维护了一个前缀和
那么我们可以对每一个节点到根节点建立前缀和,就能找任意一个节点到根节点的第K值,
那么根据主席树的性质,我们就能够计算(u,v)的路上的第K值了
只要在查询的时候稍改变一下就行了
1 | cnt = sum[ls[u]]+sum[ls[v]]-sum[ls[lca(u,v)]]-sum[ls[fa[lca(u,v)]]]; |
不理解其实可以将主席树画出来 思考下 挺好理解的.
附本题代码
——————————————————————————————————————
1 | # pragma comment(linker, "/STACK:1024000000,1024000000") |