ztr loves trees

Accepts: 5
Submissions: 83
Time Limit: 6000/2500 MS (Java/Others)
Memory Limit: 131072/65536 K (Java/Others)
问题描述
ztr神犇从小就喜欢树,CCTV-少儿“智慧树上智慧果,智慧树下你和我,智慧树前做游戏,欢乐多又多”。
有一天,qzh去找ztr问问题,给一颗有根树,树上的每一个节点有一个权值,每次询问某个子树中所有权值的中位数
ztr:这种水题还用做?qzh表示很无奈,于是qzh找到了神犇的你,你能帮帮他吗?
输入描述
第一行一个正整数T,为数据组数.
每组数据第一行读入两个正整数n,m,分别表示树上的节点数和询问次数.
接下来n个数,第i个数表示编号为i的节点权值val
接下来n-1行,每行两个数u,v表示从u到v有一条边.
接下来m行,每行一个数x表示询问以x为根的子树中所有权值的中位数.
$1<=T<=3,1<=n<=10^{5},1<=m<=10^{6},1<=u<=v<=n,1<=val<=10^{9}$,1号节点是树的根,保证输入是棵有根树
输出描述
对于每一组数据,输出一行,为了避免输出巨大,你需要把每一个询问后的数hash之后再输出
hash的方法:a[i]表示第i个询问结果 $ans = \sum a[i]*10^{m-i}\;mod\;1,000,000,007$输出保留一位小数
输入样例
1
5 3
1 2 3 4 5
1 2
2 3
3 4
4 5
1
2
3
输出样例
339.0
Hint
你需要读入优化