Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:256 MB

#2899. sshzm

统计

三怂HZM

(sshzm)

4s/256M

【问题描述】

HZM有一妹子,某天HZM考试AK了,跑去吃饭。

在饭店遇到妹子了,妹子问:“呀你怎么在这里。”对曰:“我没洗碗。”

对于这个回答。

妹子很生气。

HZM决定安慰她。

HZM的妹子非常喜欢apple pen。这个笔的构造很奇怪,它有多种笔芯。也就是说,这个笔构成了一个树。每支笔芯对应树上的一段路径,每支笔芯当然也会有一个好看度。现在妹子想只用树上的一段路径来写字,所以就会有多个包含了这条路径的笔芯,妹子会从中选出好看度第k小的来写字,询问HZM这个好看度是多少。

因为HZM忙着出计算几何的毒瘤题,他把这个任务交给了你。

简单题意:有一棵n个结点的树,给出其中的m条权值路径,给出q个询问,每个询问输出包含这条权值路径的询问路径中第k小的权值。

【输入格式】

第一行三个整数n,m,q对应问题描述。

第二至n行每行两个整数表示一点边。

接下来m行每行三个整数u,v,k,表示权值路径及其权值。

接下来q行每行三个整数u,v,k,表示询问路径及查询的第k小。

【输出格式】

q行,每行一个整数,表示对t个询问的答案

【样例1输入】

10 10 10

1 2

2 3

1 4

4 5

4 6

1 7

4 8

7 9

1 10

3 4 8458481

5 6 1498117

7 8 227646

1 8 3923041

5 10 6398537

7 10 72814

6 9 6321617

5 6 8027009

6 7 1056642

8 9 9692641

4 3 1

9 8 3

6 5 2

6 5 2

10 5 1

9 6 2

6 5 2

6 5 2

7 6 1

10 7 1

【样例1输出】

8458481

9692641

8027009

8027009

6398537

6321617

8027009

8027009

1056642

72814

【子任务】

测试点 n m q 备注

1,2 n<=3000 m<=3000 q<=3000 无

3,4,5 n<=40000 m<=40000 q<=40000 数据成一条链状

6,7,8,9,10 n<=40000 m<=40000 q<=40000 无

样例