http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1505. 树(张闻涛)
时间限制:1.0s   内存限制:512.0MB  
总提交次数:199   AC次数:67   平均分:58.74
将本题分享到:
   
 
问题描述
  给定一棵N个节点的树,每个点有一个权值,有M个询问(a,b,c)若a 为1,回答b到c路径上的最小权值,若a为2,回答b到c路径上的最大权值,若a为3,回答b到c路径上的所有权值的中位数,k个数的中位数定义为从0到k-1编号从小到大排序后k/2号的那个数。
输入格式
  第一行两个整数N,M
  第二行N个整数,v[1]~v[n],代表每个节点的权值。
  接下来N-1行每行两个整数x,y代表x和y有一条边
  最后M行每行三个整数a,b,c,表示一组询问。
输出格式
  共M行,每行一个整数,代表询问的答案。
样例输入
5 3
1 3 2 4 5
1 2
2 4
4 3
4 5
1 1 5
2 1 3
3 1 5
样例输出
1
4
4
数据规模和约定
  共20个数据
  数据1~3 N,M<=1000
  数据4~6 N,M<=5000
  数据7~10 N,M<=10000
  数据11~18 N,M<=30000
  数据19~20 N,M<=100000