# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
230450123 |
Practice:
Cypher70 |
1882D
- 26
|
C++17 (GCC 7-32)
|
Accepted
|
2058 ms
|
106632 KB
|
2023-10-30 09:06:10 |
2023-10-30 09:06:10 |
|
#include <bits/stdc++.h>
#ifdef LOCAL
#include "Debugger/Debug.h"
#endif
void test_case() {
int n;
std::cin >> n;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) std::cin >> a[i];
std::vector<std::vector<int>> adj(n+1);
for (int i = 1; i < n; ++i) {
int u, v;
std::cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
std::vector<int> size(n+1), parent(n+1);
std::function<void(int, int)> dfs1 = [&] (int v, int p) {
parent[v] = p;
size[v] = 1;
for (int e: adj[v]) {
if (e == p) continue;
dfs1(e, v);
size[v] += size[e];
}
};
dfs1(1, -1);
std::vector dp(20, std::vector<long long>(2 * (n+1)));
for (int pos = 0; pos < 20; ++pos) {
std::function<void(int)> dfs2 = [&] (int v) {
int k = (a[v] >> pos) & 1;
for (int e: adj[v]) {
if (e != parent[v]) dfs2(e);
}
if (k == 0) {
dp[pos][(v << 1) + 1] += size[v] * (1LL << pos);
for (int e: adj[v]) {
if (e == parent[v]) continue;
dp[pos][v << 1] += dp[pos][e << 1];
dp[pos][(v << 1) + 1] += dp[pos][e << 1];
}
} else {
dp[pos][v << 1] += size[v] * (1LL << pos);
for (int e: adj[v]) {
if (e == parent[v]) continue;
dp[pos][v << 1] += dp[pos][(e << 1) + 1];
dp[pos][(v << 1) + 1] += dp[pos][(e << 1) + 1];
}
}
};
dfs2(1);
}
std::vector<long long> ans(n+1);
std::function<void(int, int, long long, long long)> dfs3 = [&] (int pos, int v, long long zero, long long one) {
int k = (a[v] >> pos) & 1;
long long x = dp[pos][v << 1], y = dp[pos][(v << 1) + 1];
if (k == 0) {
y += (n - size[v]) * (1LL << pos);
x += zero, y += zero;
ans[v] += std::min(x, y);
for (int e: adj[v]) {
if (e == parent[v]) continue;
long long x1 = x, y1 = y - size[e] * (1LL << pos);
x1 -= dp[pos][e << 1], y1 -= dp[pos][e << 1];
dfs3(pos, e, x1, y1);
}
} else {
x += (n - size[v]) * (1LL << pos);
x += one, y += one;
ans[v] += std::min(x, y);
for (int e: adj[v]) {
if (e == parent[v]) continue;
long long x1 = x - size[e] * (1LL << pos), y1 = y;
x1 -= dp[pos][(e << 1) + 1], y1 -= dp[pos][(e << 1) + 1];
dfs3(pos, e, x1, y1);
}
}
};
for (int i = 0; i < 20; ++i) dfs3(i, 1, 0, 0);
for (int i = 1; i <= n; ++i) std::cout << ans[i] << " ";
std::cout << '\n';
}
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cout.tie(nullptr)->sync_with_stdio(false);
int t = 1;
std::cin >> t;
while (t--) test_case();
return 0;
}
Click to see test details