Question meaning
There is one
n
n
A tree of n nodes, each node has a weight
a
i
a_i
ai?, now we need to perform the following operations several times to change the point weight of each point on the tree to all the same.
- Assume that a certain point is used as the root of the tree, and a point is selected
v
v
v and a nonnegative integer
c
c
c , move the node
v
v
The point weights of all points on the subtree of v become
a
i
?
c
a_i \bigoplus c
aic ,cost is
s
?
c
s \cdot c
s?c,
s
s
s stands for
v
v
Number of nodes in the subtree of v
given respectively as
n
n
Minimum cost with n points as roots
Ideas
First consider the situation with a certain point as the root: Assume that the node
v
v
v’s father is
f
a
v
fa_v
fav?, it was observed that: in order to make
a
f
a
v
?
a
v
=
0
a_{fa_v} \bigoplus a_v = 0
afav?av?=0, it must be changed
a
v
a_v
The value of av?, that is: in
v
v
Select once on v
c
=
a
v
?
a
f
a
v
c = a_v \bigoplus a_{fa_v}
Operation of c=avafav. So in this way, you can operate from the bottom of the tree all the way up, which must be optimal. Then the answer is:
∑
v
≠
r
o
o
t
s
v
×
(
a
v
?
a
f
a
v
)
\sum_{v \\
eq root} s_v \times (a_v \bigoplus a_{fa_v})
∑v=root?sv?×(avafav)
Next consider the situation of changing roots: if the previous root is
r
r
r , now replaced by a new root adjacent to it
q
q
q. So
q
q
q and
r
r
The contribution of the subtrees of r to the answer will not change, the only thing that changes is
q
q
q and
r
r
r’s contribution. by
r
r
When r is the root,
q
q
q’s contribution to the answer is
(
a
q
?
a
r
)
×
s
q
(a_q \bigoplus a_r) \times s_q
(aqar?)×sq?, will
q
q
After q becomes the new root,
q
q
q will not contribute to the answer, so the new answer must be subtracted
(
a
q
?
a
r
)
×
s
q
(a_q \bigoplus a_r) \times s_q
(aqar?)×sq?. In the same way, with
r
r
When r is the root,
r
r
r did not contribute to the answer, but changed
q
q
After q is the root,
r
r
r’s contribution to the answer is
(
a
r
?
a
q
)
×
(
n
?
s
q
)
(a_r \bigoplus a_q) \times (n-s_q)
(araq?)×(n?sq?) should be added.
// Problem: D. Tree XOR
// Contest: Codeforces - Codeforces Round 899 (Div. 2)
// URL: https://codeforces.com/contest/1882/problem/D
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc + + .h>
#define fore(i,l,r) for(int i=(int)(l);i<(int)(r); + + i)
#define first
#define se second
#define endl '\\
'
const int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;
typedef long long ll;
const int N=200050;
ll num[N]; //Subtree size
int a[N];
std::vector<int> edge[N];
ll ans[N];
int n;
void dfs1(int u,int fa){<!-- -->
num[u] = 1;
for(auto v : edge[u])
if(v != fa){<!-- -->
dfs1(v,u);
num[u] + = num[v];
}
}
void dfs2(int u,int fa){<!-- -->
if(u != 1) ans[1] + = (a[u] ^ a[fa])*num[u];
for(auto v : edge[u])
if(v != fa)
dfs2(v,u);
}
void dfs3(int u,int fa){<!-- -->
if(u != 1){<!-- -->
ans[u] = ans[fa];
ans[u] -= (a[u] ^ a[fa])*num[u];
ans[u] + = (a[u] ^ a[fa])*(n - num[u]);
}
for(auto v : edge[u])
if(v != fa)
dfs3(v,u);
}
int main(){<!-- -->
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int t;
std::cin>>t;
while(t--){<!-- -->
std::cin>>n;
fore(i,1,n + 1) std::cin>>a[i];
fore(i,1,n + 1){<!-- -->
ans[i] = num[i] = 0;
edge[i].clear();
}
fore(i,1,n){<!-- -->
int u,v;
std::cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs1(1,0); //for num[]
\t
dfs2(1,0); //solve ans[1] first
\t
dfs3(1,0); //root change
\t
fore(i,1,n + 1) std::cout<<ans[i]<<" \\
"[i==n];
}
return 0;
}