ARC C求调
  • 板块学术版
  • 楼主Albert_Wei
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/5/28 22:03
  • 上次更新2023/10/23 14:24:49
查看原帖
ARC C求调
676634
Albert_Wei楼主2023/5/28 22:03
#include <bits/stdc++.h>
#define int long long
using namespace std;

bool flag;
vector<int> e[200005];
char s[200005], c[200005];
int t, n, pr[200005], w[200005], b[200005];
inline void dfs1(int x) {
 for (int i = 0; i < e[x].size(); i++)
  if (e[x][i] != pr[x]) {
   pr[e[x][i]] = x;
   dfs1(e[x][i]);
  }
}

inline void dfs2(int x) {
 if (e[x].size() == 1) {
  c[x] = s[pr[x]];
  if (s[pr[x]] == 'W') w[pr[x]]++;
  if (s[pr[x]] == 'B') b[pr[x]]++;
  return ;
 }
 for (int i = 0; i < e[x].size(); i++)
  if (e[x][i] != pr[x]) {
   dfs2(e[x][i]);
   if (s[e[x][i]] == 'W') {
   	if (w[e[x][i]] < b[e[x][i]]) flag = false;
   	if (w[e[x][i]] == b[e[x][i]]) {
   	 if (c[x] == 'x') c[x] = 'W', w[pr[x]]++;
   	 if (c[x] == 'B') flag = false;
	}
   } 
   if (s[e[x][i]] == 'B') {
   	if (w[e[x][i]] > b[e[x][i]]) flag = false;
   	if (w[e[x][i]] == b[e[x][i]]) {
   	 if (c[x] == 'x') c[x] = 'B', b[pr[x]]++;
   	 if (c[x] == 'W') flag = false;
	}
   } 
   if (c[x] == 'x') {
    c[x] = s[pr[x]];
    if (s[pr[x]] == 'W') w[pr[x]]++;
    if (s[pr[x]] == 'B') b[pr[x]]++;
   }
  }
}

signed main() {
 cin >> t;
 while (t--) {
  cin >> n;
  flag = true;
  for (int i = 1; i <= n; i++)
   pr[i] = w[i] = b[i] = 0, c[i] = 'x', e[i].clear();
  for (int i = 1, a, b; i < n; i++) {
   cin >> a >> b;
   e[a].push_back(b), e[b].push_back(a);
  }
  cin >> s + 1;
  dfs1(1); dfs2(1);
  if (!flag) cout << -1 << endl;
  else for (int i = 1; i <= n; i++) cout << c[i];
  cout << endl;
 }
 return 0;
}

2023/5/28 22:03
加载中...