传送门
题意
给出一颗树，节点编号为 $1 ... n$，每个点有一个权值 $a_i$。
你可以执行任意次操作：选择一个 $x$ 满足 $1 \le i \le n$，和一个正整数 $c$。并将 $x$ 子树中所有点的权值异或上 $c$，这次操作的代价为 $u \cdot c$，其中 $u$ 为子树 $x$ 的节点个数。
现在需要你求出，对于每个 $r,1 \le r \le n$，以 $r$ 为根时，让所有 $a_i$ 相等的最小代价。
$1 \le n \le 2 \cdot 10 ^ 5,1 \le a_i \le 2 ^ {20}$
题解
我们首先考虑，只需要求出以 $1$ 为根时的答案。
看到异或操作，而且 $a \le 2 ^ {20}$，可以想到对每一位分别处理。
接下来我们考虑树形DP，设 $f_{x,j,k}$ 表示将子树 $x$ 所有点权值的第 $j$ 位均变成 $k$ 的方案数，那么答案就是 $\sum_{j=0}^{20} {\min \{f_{1,j,0},f_{1,j,1}\}}$。
对于一个叶子节点，可以很容易地求出它的 $f$ 值。
对于任意非叶子节点 $x$。
若 $x$ 的第 $j$ 位为 $1$
- 若要子树内所有点第 $j$ 位均为 $1$。我们必须在 $x$ 上进行偶数次操作，而偶数次异或不仅不会改变权值，而且会增加代价，所以我们不在 $x$ 上操作。有 $f_{x,j,1} = \sum_{y \in Son(x)}f_{y,j,1}$
- 若要子树内所有点第 $j$ 位均为 $0$。我们必须对 $x$ 上进行奇数次操作，而奇数次操作与 $1$ 次操作的影响一样，但代价更多，所以我们只在 $x$ 上进行一次操作。有 $f_{x,j,0} = \sum_{y \in Son(x)}f_{y,j,0} + 2 ^ {j - 1} \cdot size_x$
对于 $x$ 的第 $j$ 位为 $0$ 时类似。
于是我们可以写出这个简化版问题的部分代码。
const int maxn = 200010;
int t, n, a[maxn];
int f[maxn][22][2], s[maxn][22][2], siz[maxn];
vector <int> e[maxn];
void dfs (int x, int fa) {
siz = 1;
for (int y : e) {
if (y != fa){
dfs (y, x);
siz += siz[y];
for (int j = 0; j < 20; j++) {
s[j][0] += f[y][j][0];
s[j][1] += f[y][j][1];
}
}
}
for (int j = 0; j < 20; j++) {
if ((a >> j) & 1) {
f[j][1] = s[j][1];
f[j][0] = f[j][1] + siz * (1 << j);
} else {
f[j][0] = s[j][0];
f[j][1] = f[j][0] + siz * (1 << j);
}
}
}考虑完整问题。
我们需要求出每个点作为根的情况。可以做换根dp。设 $g_{x,j,k}$ 表示以 $x$ 为根，第 $j$ 位均为 $k$ 的最小代价。
要求出点 $x$ 作为根时的答案，我们可以从以 $fa_x$ 为根的答案转移过来。（这里的父子关系指的是在以 $1$ 为根时）。
考虑如何将 $g_{fa_x,j,0/1}$ 转移到 $g_{x,j,0/1}$，进行分讨论。
若 $x$ 的第 $j$ 位为 $1$
若 $fa_x$ 的第 $j$ 位为 $1$，根据上面计算的方法，我们直接算出 $g_{fa_x,j,1}$ 去掉子树 $x$ 时的答案，再加上 $x$ 所有儿子的代价。
- $g_{x,j,1}=g_{fa,j,1}-f_{x,j,1}+\sum_{y \in Son(x)}{f_{y,j,1}}=g_{fa,j,1}-f_{x,j,1}+f_{x,j,1}=g_{fa,j,1}$。
$g_{x,j,0}=g_{x,j,1}+2^{j-1}\cdot n$。
若$fa_x$的第$j$位为 $0$，我们需要先把$fa_x$作为根时除子树$x$的部分第$j$位都变成$1$，把$x$的所有儿子变成第$j$位变成$1$。
- $g_{x,j,1}=g_{fa_x,j,1}-f_{x,j,0}-siz_x*2^{j-1}+\sum_{y \in Son(x)}{f_{y,j,1}}$。
$g_{x,j,0}$相当于在$g_{x,j,1}$的基础上多在$x$上做了个操作。
- $g_{x,j,0}=g_{x,j,1}+2^{j-1}\cdot n$。
对于$x$的第$j$位为$0$也同理。
完整代码
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define int long long
const int maxn = 200010;
int t, n, a[maxn];
int f[maxn][22][2], res[maxn], g[maxn][22][2], siz[maxn], s[maxn][22][2];
vector <int> e[maxn];
void dfs (int x, int fa) {
siz = 1;
for (int y : e) {
if (y != fa){
dfs (y, x);
siz += siz[y];
for (int j = 0; j < 20; j++) {
s[j][0] += f[y][j][0];
s[j][1] += f[y][j][1];
}
}
}
for (int j = 0; j < 20; j++) {
if ((a >> j) & 1) {
f[j][1] = s[j][1];
f[j][0] = f[j][1] + siz * (1 << j);
} else {
f[j][0] = s[j][0];
f[j][1] = f[j][0] + siz * (1 << j);
}
}
}
void dp (int x, int fa) {
if (fa) {
for (int j = 0; j < 20; j++) {
if ((a >> j) & 1) {
if ((a[fa] >> j) & 1) {
g[j][1] = g[fa][j][1];
g[j][0] = g[j][1] + n * (1 << j);
} else {
g[j][1] = g[fa][j][1] - f[j][0] - siz * (1 << j) + s[j][1];
g[j][0] = g[j][1] + n * (1 << j);
}
} else {
if ((a[fa] >> j) & 1) {
g[j][0] = g[fa][j][0] - f[j][1] - siz * (1 << j) + s[j][0];
g[j][1] = g[j][0] + n * (1 << j);
} else {
g[j][0] = g[fa][j][0];
g[j][1] = g[j][0] + n * (1 << j);
}
}
res += min (g[j][0], g[j][1]);
}
}
for (int y : e) {
if (y != fa) dp (y, x);
}
}
signed main () {
cin.tie (0) -> sync_with_stdio (false);
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 20; j++) {
f[i][j][0] = f[i][j][1] = 0;
g[i][j][0] = g[i][j][1] = 0;
s[i][j][0] = s[i][j][1] = 0;
}
res[i] = siz[i] = 0;
cin >> a[i];
e[i].clear ();
}
for (int i = 1; i < n; i++) {
int x, y; cin >> x >> y;
e.push_back (y);
e[y].push_back (x);
}
dfs (1, 0);
for (int i = 0; i < 20; i++) {
res[1] += min (f[1][i][0], f[1][i][1]);
g[1][i][0] = f[1][i][0];
g[1][i][1] = f[1][i][1];
}
dp (1, 0);
for (int i = 1; i <= n; i++) cout << res[i] << ' ';
cout << '\n';
}
return 0;
}