三怂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 无