shunfurh
编程介的小学生
2017-10-17 14:17

动态树

  • e5
  • each

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

  • 点赞
  • 回答
  • 收藏
  • 复制链接分享

1条回答

为你推荐

换一换