Atcoder [ARC161C] Dyed by Majority (Odd Tree) 题解 [ 绿 ] [ 树的遍历 ] [ 构造 ] [ 贪心 ]

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;
}