P9745 「KDOI-06-S」树上异或题解

喵仔牛奶 · 2023-10-15 19:41:24 · 题解

Solution

树形 DP 好题。

Part I 部分分类比

下文为简单，我们称一个连通块的权值为连通块内点的异或和。

考虑链的部分分，显然可以设 f_{i} 是前 i 个点所有断边方案的权值和，对于每个点枚举上一条断的边转移。令 s_i=\bigoplus_{j=1}^{i}a_j，则 f_i=\sum_{j=0}^{i-1}(s_i\oplus s_{j})\times f_j。

这样是 \mathcal{O}(n^2) 的，我们拆位算贡献，就可以做到 \mathcal{O}(n\log V)。

具体地，设 g_{i,j,k} 是所有断边方案中，与 i 相连的连通块的价值在二进制下第 j 位是 k 的，不与 i 相连的连通块的价值乘积的和。

初始状态：若 a_u 第 j 位为 1，则 g_{i,j,1}=1，否则 g_{i,j,0}=1。

转移如下：

为了避免后效性，先保存 t_0=g_{i,j,0},t_1=g_{i,j,1}。
g_{i,j,0}=t_{0}\times(g_{i-1,j,0}+f_{i-1})+t_{1}\times g_{i-1,j,1}\\ g_{i,j,1}=t_{0}\times g_{i-1,j,1}+t_{1}\times (g_{i-1,j,0}+f_{i-1})\\ f_{i}=\sum_{j=0}^{63}2^j\times g_{i,j,1} \end{cases}

同理，对于树我们也通过断边来转移。

Part II 解决问题

设 f_{u} 是以 u 为根的子树的所有断边方案的权值和。

为了转移，再设 g_{u,i,j} 是以 u 为根的子树里断开若干边，所有断边方案中，与 u 相连的连通块的价值在二进制下第 i 位是 j 的，不与 u 相连的连通块的价值乘积的和。

初始状态：若 a_u 第 i 位为 1，则 g_{u,i,1}=1，否则 g_{u,i,0}=1。

对于每个儿子，枚举二进制下每位 i 转移。

不断儿子相当于当前连通块的异或和第 i 位异或上儿子连通块的第 i 位，断掉儿子相当于异或上 0。
为了避免后效性，先保存 t_0=g_{u,i,0},t_1=g_{u,i,1}。
g_{u,i,0}\gets t_0\times(g_{v,i,0}+f_{v})+t_1\times g_{v,i,1} \\ g_{u,i,1}\gets t_0\times g_{v,i,1}+t_1\times(g_{v,i,0}+f_{v}) \end{cases}

转移完后，f_{u} 就可以简单地计算啦。

答案显然就是 f_{1}。

Part III 小结

不难发现该算法时空复杂度均为 \mathcal{O}(n\log V)，需要将 g_{u,i,j} 用 int 类型保存才能通过。

启示：

树形 DP 的题可以用链的部分分类比得出正解。
树形 DP 需要想清楚状态、列明白转移方程再写，否则在调试过程中通常会越写越复杂，导致耗费大量时间而最终一分也不得。

Code

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
using namespace std;
namespace Milkcat {
    typedef long long LL;
    typedef pair<LL, LL> pii;
    const int N = 1e6 + 5, mod = 998244353;
    LL n, u, v, a[N], f[N]; int g[N][64][2];
    vector<int> G[N];
    void dfs(int u, int fa) {
        REP(i, 0, 63) g[u][i][a[u] >> i & 1] = 1;
        for (int v : G[u]) {
            if (v == fa) continue;
            dfs(v, u);
            REP(i, 0, 63) {
                LL t0 = g[u][i][0], t1 = g[u][i][1];
                g[u][i][0] = (t0 * (g[v][i][0] + f[v]) + t1 * g[v][i][1]) % mod;
                g[u][i][1] = (t0 * g[v][i][1] + t1 * (g[v][i][0] + f[v])) % mod;
            }
        }
        REP(i, 0, 63) f[u] = (f[u] + (1LL << i) % mod * g[u][i][1]) % mod;
    }
    int main() {
        cin >> n;
        REP(i, 1, n) cin >> a[i];
        REP(i, 2, n)
            cin >> u, G[u].push_back(i), G[i].push_back(u);
        dfs(1, 0);
        cout << f[1] << '\n';
        return 0;
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}

P9745 「KDOI-06-S」树上异或 题解