瑶瑶的动感光波

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

瑶瑶(tsyao)最近在练功—动感光波(适厉害呀(有错别字?)),瑶瑶有一个很大的练功房(其实是以前练舞蹈的么),练功房很大,可以分成n个区域。为了方便练功,练功房的布置很特别,所以我们可以把练功房看做以1号区域为根节点的,有n个节点的树。练功房每个区域有着不同的状态,有的区域雾气比较大,发挥动感光波的威力会消耗较大功力,有的区域很厉害,能够发挥动感光波的极大威力QAQ(惊呆了)。每个区域都会有雾气ai,雾气会消耗ai的功力,能够发挥的威力bi这两个属性。瑶瑶的动感光波更厉害了,能够分成两个叉(每次使用动感光波时只能分叉一次),分别攻击不同的区域,当然,也可以不分叉。瑶瑶每次会选择一个区域z,然后再选择另外两个区域x和y,向x,y发出动感光波。这里,瑶瑶选择的z一定是x和y的祖先。

由于瑶瑶偷懒,不喜欢练功,因此她功力有限,每次发动动感光波途径一些区域时,会纠结是否在改区域消耗功力来获取威力(伤害?)。

给出m个查询,每次输入z,x,y,w四个整数,其中w为使用的功力。萌萌的瑶瑶想知道每次能够发挥最大为多少的威力。

Input

第一行 两个整数n,m 。

接下来n行,每行两个整数ai,bi,表示第i号区域的两个属性。

接下来n-1行,每行两个整数ci,di,表示区域ci与区域di相接。

接下来m行,每行四个整数z,x,y,w。

Output

m行,每行输出每个询问的答案。

Sample Input

9 1
50 100
1 1
30 1
30 1
1 1
50 100
1 1
50 100
30 1
1 2
2 3
3 4
3 5
3 6
4 7
4 8
5 9
2 7 9 31

Sample Output

3

Hint

图片为样例解释:

对于 100%的数据,有1 ≤ n ≤ 3000 , 1 ≤ m ≤ 1000 , 1 ≤ ai ≤ 50 , 1 ≤ bi ≤ 1000 , 1 ≤ x,y,z,ci,di ≤ n , 1 ≤ w ≤ 50 。

单组输入,共5组数据。

加强版题目在http://acdream.info/problem?pid=1119

Source

tsyao

Manager

Information
Solved Number50
Submit Number110
Problem Tags
data structures
dfs and similar
dp
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel