# [bzoj 2809][Apio2012]dispatching

## Description

1  ≤N ≤ 100,000 忍者的个数；
1  ≤M ≤ 1,000,000,000 薪水总预算；
0  ≤Bi < i  忍者的上级的编号；
1  ≤Ci ≤ M                     忍者的薪水；
1  ≤Li ≤ 1,000,000,000             忍者的领导力水平。

# [bzoj 1803][Spoj 1487]Query on a tree III

## Description

You are given a node-labeled rooted tree with n nodes. Define the query (x, k): Find the node whose label is k-th largest in the subtree of the node x. Assume no two nodes have the same labels.

## Input

The first line contains one integer n (1 <= n <= 10^5). The next line contains n integers li (0 <= li <= 109) which denotes the label of the i-th node. Each line of the following n - 1 lines contains two integers u, v. They denote there is an edge between node u and node v. Node 1 is the root of the tree. The next line contains one integer m (1 <= m <= 10^4) which denotes the number of the queries. Each line of the next m contains two integers x, k. (k <= the total node number in the subtree of x)

# [hdu 2665][poj 2104] 区间第K大

## Problem Description

Give you a sequence and ask you the kth big number of a inteval.

## Input

The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]