音无彩名给你一个数组 AA，以及一棵 nn 个节点的树，每个点有一个颜色，颜色为 11 到 xx 的整数。 有 mm 次查询，每次查询树上只保留 [l,r][l,r] 内的所有节点，设一个极大连通块中出现奇数次数的颜色个数为 tt，则其对答案的贡献为 A_tA t ​ ，即答案是所有连通块贡献的和，询问间互相独立。 输入格式 第一行三个用空格隔开的数 n,m,xn,m,x。 第二行 nn 个数表示每个点的颜色。 之后 n-1n−1 行每行两个用空格隔开的数 x,yx,y 表示一条边。 之后一行 x+1x+1 个数表示 A_0A 0 ​ 到 A_xA x ​ 。 之后 mm 行，每行两个用空格隔开的数 l,rl,r 表示一次询问。 输出格式 输出 mm 行，每行一个数表示这次询问的答案。 输入输出样例 输入 #1复制 6 3 5 1 1 4 5 1 4 1 2 2 3 3 4 4 5 5 6 1 1 4 5 1 4 1 1 4 5 1 4 输出 #1复制 1 4 4代码

from collections import Counter

class Edge:
    def __init__(self, v, w, nxt):
        self.v, self.w, self.nxt = v, w, nxt

class Tree:
    def __init__(self, n, h):
        self.head = [-1] * n
        self.edges = []
        self.idx = 0
        self.h = h

    def add(self, v, w):
        self.edges.append(Edge(v, w, self.head[self.h[v]]))
        self.head[self.h[v]] = self.idx
        self.idx += 1

def dfs1(u, fa, h, sz, son):
    sz[u] = 1
    for i in range(h[u], -1, -1):
        v = tree.edges[tree.head[i]].v
        if v == fa:
            continue
        dfs1(v, u, h, sz, son)
        sz[u] += sz[v]
        if sz[v] > sz[son[u]]:
            son[u] = v

def dfs2(u, fa, h, top, idx):
    top[u] = idx
    idx += 1
    if son[u]:
        dfs2(son[u], u, h, top, idx)
    for i in range(h[u], -1, -1):
        v = tree.edges[tree.head[i]].v
        if v == fa or v == son[u]:
            continue
        dfs2(v, u, h, top, idx)

def add(u):
    color[u] ^= 1
    if color[u]:
        cnt[a[u]] += 1
        if cnt[a[u]] % 2 == 1:
            odd_color.add(a[u])
        else:
            odd_color.discard(a[u])
    else:
        cnt[a[u]] -= 1
        if cnt[a[u]] % 2 == 1:
            odd_color.add(a[u])
        else:
            odd_color.discard(a[u])

def query(u, v):
    global res
    while top[u] != top[v]:
        if dep[top[u]] < dep[top[v]]:
            u, v = v, u
        res += A[cnt_color[top[u]] ^ len(odd_color)]
        add(top[u])
        u = fa[top[u]]
    if dep[u] > dep[v]:
        u, v = v, u
    res += A[cnt_color[u] ^ len(odd_color)]
    for i in range(h[u], -1, -1):
        x = tree.edges[tree.head[i]].v
        if x == fa[u]:
            continue
        if x == v:
            break
        add(x)

n, m, x = map(int, input().split())
a = [0] + list(map(int, input().split()))
tree = Tree(n + 1, [0] * (n + 1))
for i in range(n - 1):
    u, v = map(int, input().split())
    tree.add(u, v)
    tree.add(v, u)
A = [0] + list(map(int, input().split()))
dep = [0] * (n + 1)
fa = [0] * (n + 1)
sz = [0] * (n + 1)
son = [0] * (n + 1)
dfs1(1, 0, tree.head, sz, son)
dfs2(1, 0, tree.head, [0] * (n + 1), 1)
fa[1] = 0
for i in range(tree.head[1], -1, -1):
    v = tree.edges[i].v
    if v != son[1]:
        fa[v] = 1
        cnt_color[1] += 1
    else:
        fa[v] = 0
for i in range(2, n + 1):
    if not fa[i]:
        continue
    if son[fa[i]] == i:
        fa[i] = fa[fa[i]]
    top[i] = top[fa[i]]
    cnt_color[top[i]] += 1
color = [0] * (n + 1)
cnt = [0] * (x + 1)
cnt_color = [0] * (n + 1)
odd_color = set()
res = 0
queries = []
for i in range(m):
    l, r = map(int, input().split())
    queries.append((l, r, i))
queries.sort()
ans = [0] * m
l, r = 1, 0
for ql, qr, idx in queries:
    while l > ql:
        add(l - 1)
        l -= 1
    while r < qr:
        add(r + 1)
        r += 1
    while l < ql:
        add(l)
        l += 1
    while r > qr:
        add(r)
        r -= 1
    query(ql, qr)
    ans[idx] = res
print('\n'.join(map(str, ans)))