题解【P9039 [PA2021] Drzewo czerwono-czarne】

· · 题解

首先一条链的问题是简单的，每个颜色会扩展成连续一段，判断颜色段数即可。

接下来判掉颜色全部相等的情况。

剩下的情况中显然存在度数 \ge 3 的点，不妨假设其为 u，不难发现，我们总可以让其中一些儿子为黑，一些为白。不难发现，借助 u 可以任意交换、染色所有儿子，只要不全变成一个颜色。

那么直接以这个点为根，儿子可以向子树不断发出 黑/白 的脉冲，显然可以满足所有子树内的限制。最后 u 及其儿子不能够达到的情况就是 u 和所有儿子颜色都不同。

不妨假设 u 是白的，假如说能够在子树 v 的儿子上“存储”一个黑色，那么只需要最后 u,v 染白，用 v 的儿子把 v 染黑即可。不难发现，如果子树内两个颜色不是二分图的两边，那么必然存在一条边两边相同，把其到 v 的路径都往下移一个就可以存储一个黑的。

剩下可能不合法的情况就是整个树黑白是二分图的两边，判掉即可。

复杂度 O(n)。

// Problem: P9039 [PA2021] Drzewo czerwono-czarne
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9039
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// Create Time: 2023-06-08 22:10:31
// Input/Output: stdin/stdout
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define rep(i, s, t) for (int i = s; i <= t; ++i)
#define per(i, s, t) for (int i = t; i >= s; --i)

const int N = 1e5 + 5;

int n;
int a[N], b[N];
vector<int> adj[N];
int d[N];

inline void dfs(int u, int fa) {
    d[u] = d[fa] ^ 1;
    for(int v : adj[u]) if(v != fa) dfs(v, u);
}

void solve() {
    cin >> n;
    rep(i, 1, n) adj[i].clear();
    rep(i, 1, n) {
        char ch; cin >> ch; a[i] = ch - '0';
    }
    rep(i, 1, n) {
        char ch; cin >> ch; b[i] = ch - '0';
    }
    rep(i, 2, n) {
        int u, v; cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }
    bool f = 1;
    rep(i, 2, n) f &= a[i] == a[i-1];
    if(f) {
        bool ok = 1;
        rep(i, 1, n) ok &= b[i] == a[1];
        cout << (ok ? "TAK" : "NIE") << "\n";
        return;
    }
    int mx = 0;
    rep(i, 1, n) mx = max(mx, (int)adj[i].size());
    if(mx <= 2) {
        int p = -1;
        rep(i, 1, n) if(adj[i].size() == 1) p = i;
        int las = p;
        p = adj[p][0];
        int c1 = (a[las] != a[p]) - (a[las] != b[las]), c2 = (b[las] != b[p]);
        while(adj[p].size() > 1) {
            int v = adj[p][0] ^ adj[p][1] ^ las;
            c1 += a[p] != a[v];
            c2 += b[p] != b[v];
            las = p;
            p = v;
        }
        cout << (c1 >= c2 ? "TAK" : "NIE") << "\n";
        return;
    }
    f = 1;
    rep(i, 1, n) f &= a[i] == b[i];
    if(f == 1) {
        cout << "TAK" << "\n";
        return;
    }
    dfs(1, 0);
    f = 1;
    rep(i, 2, n) f &= (b[i] ^ d[i]) == (b[i-1] ^ d[i-1]);
    cout << (f ? "NIE" : "TAK") << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(15); 
    cerr << fixed << setprecision(15);

    int t; cin >> t;
    while(t--) solve();

    return 0;
}