| 题目名称 | 2790. mk和tree |
|---|---|
| 输入输出 | mktree.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 afo
于2017-09-01加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：10， 提交：29， 通过率：34.48% | ||||
 胡嘉兴 |
100 | 0.555 s | 85.96 MiB | C++ |
|
胡嘉兴 |
100 | 0.722 s | 85.01 MiB | C++ |
 AAAAAAAAAA |
100 | 0.766 s | 95.72 MiB | C++ |
|
胡嘉兴 |
100 | 0.800 s | 85.01 MiB | C++ |
 Fisher. |
100 | 0.867 s | 39.23 MiB | C++ |
 梦那边的美好ET |
100 | 1.010 s | 42.07 MiB | C++ |
|
... |
100 | 1.096 s | 42.07 MiB | C++ |
|
胡嘉兴 |
100 | 1.167 s | 85.01 MiB | C++ |
|
胡嘉兴 |
100 | 1.238 s | 85.01 MiB | C++ |
 Ostmbh |
100 | 1.279 s | 171.60 MiB | C++ |
| 关于 mk和tree 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @Ostmbh :
已修复并加强。 | ||||
|
如果哪位dalao发现数据有问题请联系蒟蒻
| ||||
【题目描述】
mk有一棵树，每个节点有一个权值 现在他想知道 u->v的树上路径中 第k大的数是多少
【输入格式】
第一行一个整数n(1<=n<=100000) 树的节点个数
第2-n行每行2个整数x,y (1<=x,y<=n)意思是x与y之间连边
第n+1行 n个整数 第i个整数vi表示第i个节点的权值
第n+2行 1个整数m(1<=m<=100000) 表示询问数
接下来m行 每行3个整数 a,b,c
意思是询问a到b的树上路径上第k大节点的权值
【输出格式】
m行 每行一个整数x 表示询问的结果
【样例输入】
6
1 2
2 3
2 4
4 5
4 6
5 7 8 6 4 3
3
3 5 2
2 5 1
5 6 3
【样例输出】
6
4
6
数据范围
30%1<=n,m<=100
50%1<=n,m<=5000
100%1<=n,m<=100000,0<=vi<=10^9,1<=x,y<=n,k
保证输入必定合法
【来源】
ryz hnsdfz集训《数据结构》例题cot