[Wannafly冬令营2018Day4]两条路径(困难版)

第一行一个正整数 $n$ 表示树的边数（$n\le 100000$）。接下来一行 $n$ 个整数表示点 $1,2,\ldots,n$ 的权值。正数 $k$ 表示权值为 $2^{k-1}$，负数 $-k$ 表示权值为 $-2^{k-1}$，$0$ 表示权值为 $0$。这一行的数字绝对值不超过 $100000$。接下来 $n-1$ 行，每行两个正整数，表示树的边。接下来一行一个正整数$Q$表示询问个数（$Q\le 20$）。接下来$Q$行每行为一个询问，包含一个正整数$x$（$1\le x\le n$），代表树上的一个点。