3613: 牛半仙的妹子树(第三轮03)
题目描述
牛半仙有n 个妹子，她们所在的位置组成一棵树，相邻两个妹子的距离为 1。 有m个妹子具有超能力，她们会影响到其他妹子。
离所有具有超能力的妹子的最短距离在 [l, r]间的妹子会受到影响， 也会具有超 能力。
这些具有能力的妹子共同形成了一个磁场。对于一个位置， 一个具有超能力的 妹子为其增加的磁场强度为妹子到这个位置的距离的平方， 一个具有超能力的 妹子为其增加的磁场强度为妹子到这个位置的距离。
现在牛半仙想知道一个位置的磁场强度有多大。
因为牛半仙对妹子们特别关心，所以他有 k个询问。
输入
第一行 5 个正整数，代表n, m, k, l, r 。
第 2 行到第 n 行每行 2 个正整数 ui, vi，代表树中存在边 (ui, vi)。 第 n + 1行有 m 个正整数，代表这些妹子有超能力。
第 n + 2行有 k个正整数，代表询问的妹子。对于每个询问， 输出一行，代表该询 问的答案。
输出
对于每个询问，输出一行，代表该询问的答案。
样例输入 复制
11 2 4 2 2
1 2
1 3
2 4
2 5
3 6
3 7
5 8
5 9
9 10
9 11
3 9
1 6 9 11样例输出 复制
14
34
20
32提示
【样例 1 说明】
图中红点为超能力,绿点为超能力
1 号点权值为1^2 + 3^2 + 1 + 3 = 14
6 号点权值为1^2 +5^2 +3+5=34
9 号点权值为0^2 +4^2 +2+2=20
11 号点权值为1^2 +5^2 +3+3=32
【数据范围】
对于 5%的数据：n, m, k ≤ 100。
对于 20%的数据：n, m, k ≤ 2000。
对于另 20%的数据：ui = i, vi = i + 1。 对于另 20%的数据：ui = 1。
对于 100%的数据：n, m, k ≤ 5 × 10^5 。