对于一颗子树，我们一定是先将其根节点所有儿子所在的子树变成相同，然后再将这颗子树变成相同。
我们设 \(f_i\) 表示第 \(i\) 个节点的父亲节点，\(siz_i\) 表示第 \(i\) 个节点的子树大小。
我们需要求 \(\displaystyle\sum_{i=1}^{n}(a_i\oplus a_{f_i})\times siz_i\)。
换根 DP 即可，时间复杂度 \(\mathcal O(n)\)。
#include <bits/stdc++.h>
using i64 = long long;
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i ++ ) {
std::cin >> a[i];
}
std::vector<std::vector<int>> adj(n);
for (int i = 0; i < n - 1; i ++ ) {
int u, v;
std::cin >> u >> v;
u --, v -- ;
adj[u].push_back(v), adj[v].push_back(u);
}
std::vector<i64> siz(n);
std::vector<i64> f(n), g(n);
auto dfs = [&](auto self, int x, int p) -> void {
siz[x] = 1;
for (auto y: adj[x]) {
if (y == p) {
continue;
}
self(self, y, x);
siz[x] += siz[y];
f[x] += f[y] + 1LL * (a[x] ^ a[y]) * siz[y];
}
};
dfs(dfs, 0, -1);
auto dfs1 = [&](auto self, int x, int p) -> void {
if (p != -1) {
g[x] = g[p] + f[p] - f[x] + 1LL * (n - 2 * siz[x]) * (a[x] ^ a[p]);
}
for (auto y: adj[x]) {
if (y == p) {
continue;
}
self(self, y, x);
}
};
dfs1(dfs1, 0, -1);
for (int i = 0; i < n; i ++ ) {
std::cout << f[i] + g[i] << " \n"[i == n - 1];
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t -- ) {
solve();
}
return 0;
}