提示: 欢迎访问OurACM平台。
Problem 2237 中位数

Accept: 38    Submit: 135
Time Limit: 1500 mSec    Memory Limit : 131072 KB

Problem Description

有一颗n个节点的树,节点编号1-n。树上每条边都有一个权值,现在给出q个询问,每次询问给出两个点u,v,表示一条端点为u,v的路径,现在要询问这条路径上的边的权值的中位数是多少,如果路径长度为偶数,那么此时有两个中位数,取较小的那个进行输出。

Input

多组数据(<=5),处理到EOF。

第一行输入两个数n、q,接下来n-1行每行三个数u,v,w,表示u和v之间有一条边,并且其权值为w,接下来q行,每行两个数u、v,表示询问的路径。

1<=n,q<=5*10^4

1<=u、v<=n,u!=v

0<=w<=10^5

Output

每组数据输出q行,每行一个数,表示答案。

Sample Input

7 7 2 1 1 3 1 2 1 4 0 4 5 1 5 6 3 5 7 4 1 3 4 1 2 4 2 5 3 5 3 6 3 7

Sample Output

2 0 0 1 1 1 1

Source

福州大学第十三届程序设计竞赛

Submit  Back  Status  Discuss