提示: 欢迎访问OurACM平台。
Problem 2245 动态树

Accept: 24    Submit: 164
Time Limit: 3000 mSec    Memory Limit : 65536 KB

Problem Description

YellowStar拥有一棵神奇的动态树,该树由n个带权结点,n-1条边构成,任意两个结点互相可达,标号为i结点的权值为Wi。

由于物质是运动的,这棵树每天都会发生一些变化,在第i天,该树权值在[l,r]的结点会发出强烈的光芒,YellowStar看到这一现象会非常的愉悦,它的愉悦值取决于:发光的这些结点构成了多少个连通子树。

现在你知道动态树在接下来m天的发光情况,请你计算出YellowStar每一天的愉悦值

Input

第一行输入T,表示有T组样例(T <= 20)

每组样例第一行为n,表示树的结点个数(1 <= n <= 1e5)

接下来n个数字W1, W2, ... , Wn (1 <= Wi <= 1e9)表示每个结点的权值

接下来n - 1行,每一行两个数字u, v (1 <= u, v <= n)表示树边

接下来一个数字m(1 <= m <= 1e5),表示m天

接下来m个询问,每个询问一行l, r (1 <= l <= r <= 1e9)表示每一天发光的结点的权值区间

Output

每组样例输出m行,表示YellowStar在这m天的愉悦值

Sample Input

1 3 1 3 2 1 2 1 3 3 1 3 1 2 2 3

Sample Output

1 1 2

Hint

long long类型请用%I64d输出

Source

FOJ有奖月赛-2017年4月(校赛热身赛)

Submit  Back  Status  Discuss