主题

主题

 
   

Successor

原题:http://acm.hdu.edu.cn/showproblem.php?pid=4366

Problem Description

Sean owns a company and he is the BOSS.The other Staff has one Superior.every staff has a loyalty and ability.Some times Sean will fire one staff.Then one of the fired man’s Subordinates will replace him whose ability is higher than him and has the highest loyalty for company.Sean want to know who will replace the fired man.

Input

In the first line a number T indicate the number of test cases. Then for each case the first line contain 2 numbers n,m (2<=n,m<=50000),indicate the company has n person include Sean ,m is the times of Sean’s query.Staffs are numbered from 1 to n-1,Sean’s number is 0.Follow n-1 lines,the i-th(1<=i<=n-1) line contains 3 integers a,b,c(0<=a<=n-1,0<=b,c<=1000000),indicate the i-th staff’s superior Serial number,i-th staff’s loyalty and ability.Every staff ‘s Serial number is bigger than his superior,Each staff has different loyalty.then follows m lines of queries.Each line only a number indicate the Serial number of whom should be fired.

Output

For every query print a number:the Serial number of whom would replace the losing job man,If there has no one to replace him,print -1.

Sample Input

1

3 2

0 100 99

1 101 100

1

2

Sample Output

2

-1

Author

FZU


题目大意:

给出一棵树。每个点两个权值(a-loyalty,b-ability),其中所有a权值不相同。

每一次查询一个节点的子树内,b比当前子树根大的,a的最大的节点编号。

如果不存在输出-1。


个人解法:


  • 线段树合并

把询问离线出来,在对应的节点上记录,表示需要查询这个节点。

维护子树以b为权值的线段树,线段树里面维护a的最大值。

上来的时候子树合并一下即可。

时间复杂度O(nlogn)。

(这题还有线段树做法——只是人懒就没写了)


  • 分块

把DFS序做出来。

对序列分块,每个块按照b排序,维护后缀a的最大值。

DFS序转换为了区间问题。于是我们对于整块的就二分查找,非整块的暴力枚举判断。

由于带一个log,所以可以调整块为O(sqrt(nlogn))。

时间复杂度O(nsqrt(nlogn))。

代码如下:

https://code.csdn.net/snippets/2298897

 
 
评论