Dyed by Majority (Odd Tree)

想起來無聊，寫起來惡心。

首先手模一下，發現葉子節點可以確定它父親的顏色。這啟示我們自底向上確定顏色。

因此考慮在已確定所有兒子的顏色時，確定自己的顏色，此時有兩種情況：

• 兒子中兩種顏色出現次數相等：此時自己被染成什么顏色取決于父節點是什么顏色。因此可以直接求出父節點被涂成的顏色。
• 兒子中兩種顏色出現次數不相等：此時自己父親的顏色不會影響自己的顏色。而為了盡可能滿足父節點的要求，因此可以將自己的顏色染為父節點的顏色。

最后判斷構造是否合法即可。時間復雜度 \(O(n)\)。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi = pair<int, int>;
const int N = 200005;
int n;
bitset<N> col;
int dp[N], tot[N][2], ans[N];
vector<int> g[N];
bool ilg = 0;
void dfs(int u, int fa)
{
    for(auto v : g[u])
    {
        if(v == fa) continue;
        dfs(v, u);
    }
    if(dp[u])
        tot[fa][ans[u]]++;
    else
    {
        ans[u] = col[fa];
        tot[fa][ans[u]]++;
    }
    if(tot[u][0] == tot[u][1])
    {
        int res = col[u];
        if(dp[fa] && ans[fa] != res) ilg = 1;
        dp[fa] = 1;
        ans[fa] = res;
    }
    else
    {
        if(col[u] == 0 && tot[u][0] < tot[u][1]) ilg = 1;
        if(col[u] == 1 && tot[u][0] > tot[u][1]) ilg = 1;
    }
}
void solve() 
{
    cin >> n;
    for(int i = 0; i <= n; i++)
    {
        g[i].clear();
        dp[i] = tot[i][0] = tot[i][1] = 0;
    }
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        col[i] = (c == 'B');
    }
    ilg = 0;
    dfs(1, 0);
    if(ilg || dp[0])
    {
        cout << "-1\n";
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(ans[i]) cout << 'B';
        else cout << 'W';
    }
    cout << "\n";
}
int main()
{
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}