题解：P7732 [JDWOI-2] 红黑树

Nights_watcher · 2025-04-05 08:51:56 · 题解

一眼看到 n\le20，便可以想到状压 DP。

很显然，dp_{i,j} 表示第 i 秒，状态是否可以为 j。但是如果按照常规方法转移，时间复杂度为 O(Qn^32^n)，直接爆炸。

于是我们想一下优化。我们可以将现有的所有操作都延迟一秒去做，这样它们影响的总时间不变，这时再在第一秒插入一个新的操作，这样影响的时间就为现在枚举到的时间。

我们可以预处理出一个数组表示在每个点使用魔法后每秒影响到的状态。转移时异或即可。

代码如下

#include <bits/stdc++.h>
using namespace std;
int q , n , fa[21] , s[21][21];
bool dp[21][1 << 20];
string S;
vector <int> ve[21];
void dfs (int u , int f)
{
    fa[u] = f;
    for (int v : ve[u])
        if (v != f) dfs (v , u);
}
int main ()
{
    ios :: sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);
    cin >> q;
    while (q --)
    {
        cin >> n >> S;
        for (int i = 1;i <= n;i ++) ve[i].clear ();
        for (int i = 1;i < n;i ++)
        {
            int u , v;
            cin >> u >> v;
            ve[u].push_back (v);
            ve[v].push_back (u);
        }
        dfs (1 , 0);
        for (int i = 1;i <= n;i ++)
            for (int j = 1 , k = i;j <= n;j ++ , k = fa[k])
                if (k) s[i][j] = s[i][j - 1] ^ (1 << k - 1);
                else s[i][j] = s[i][j - 1];
        int ed = 0;
        for (int i = 1;i <= n;i ++)
        {
            char c;
            cin >> c;
            if (c != S[i - 1]) ed ^= (1 << (i - 1));
        }
        dp[0][0] = 1;
        for (int i = 0;i <= n;i ++)
        {
            if (dp[i][ed])
            {
                cout << i << "\n";
                memset (dp[i] , 0 , sizeof (dp[i]));
                break;
            }
            for (int j = 0;j < (1 << n);j ++)
                if (dp[i][j])
                {
                    dp[i][j] = 0;
                    dp[i + 1][j] = 1;
                    for (int k = 1;k <= n;k ++) dp[i + 1][j ^ s[k][i + 1]] = 1;
                }
        }
    }
    return 0;
}