描述

给出一棵树，N个点，点有点权
M个询问
问以a为根b的子树点权和

输入

第一行：两个正整数N、M
第二行：N个数V_1、V_2、...、V_N为各点点权
接下来N-1行：每行两个整数a、b表示树上的一条边
接下来M行：每行两个整数a、b表示一个询问

输出

M行
对于一个询问
输出一个整数ANS

样例1

输入

6 5
1 2 3 4 5 6
1 2
1 3
5 2
4 2
6 3
5 2
4 2
6 2
6 1
2 1

输出

16
17
11
12
10

范围

40% 1<=N,M<=100
80% 1<=N,M<=1000
100% 1<=N,M<=1000000 1<=V_i<=500

限制

2000ms
128M