竞赛讨论区 > 跟着题解的思路写TLE不知道是哪里错了,C白魔法师
头像
马角的逆袭
编辑于 2020-05-18 11:02
+ 关注

跟着题解的思路写TLE不知道是哪里错了,C白魔法师

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN (200020)
#define int long long int
#define INF (0x7f7f7f7f)
#define QAQ (0)

#pragma GCC optimize(2)

using namespace std;

#ifdef debug
#define show(x...) \
do { \
cout << "\033[31;1m " << #x << " -> "; \
err(x); \
} while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

int n, m, Q, K, pre[MAXN], sum[MAXN];

vector<int> G[MAXN];
char color[MAXN];

int fa(int x) {
int ret = x;
while(~pre[ret]) ret = pre[ret];
if(ret != x) pre[x] = ret;
return ret;
}

void union_xy(int x, int y) {
int rx = fa(x), ry = fa(y);
if(rx != ry) {
sum[rx] += sum[ry];
pre[ry] = rx;
}
}

void init() {
memset(pre, -1, sizeof(pre));
for(int i=1; i<=n; i++) sum[i] = color[i]=='W';
}

signed main() {
#ifdef debug
freopen("test", "r", stdin);
clock_t stime = clock();
#endif
scanf("%lld %s ", &n, color+1);
init();

for(int i=1, u, v; i<n; i++) {
scanf("%lld %lld ", &u, &v);
G[u].push_back(v), G[v].push_back(u);
if(color[u] == color[v] && color[u] == 'W')
union_xy(u, v);
}

for(int i=1; i<=n; i++)
if(color[i] == 'W') sum[i] = sum[fa(i)];

int ans = 0;
for(int i=1; i<=n; i++) {
if(color[i] == 'B') {
int tmax = 1;
for(auto v : G[i]) {
//                show(color[v], tmax, sum[fa(v)], fa(v));
if(color[v] == 'W') tmax += sum[v];
}
ans = max(tmax, ans);
}
}
//    forarr(pre, 1, n);
//    forarr(sum, 1, n);
printf("%lld\n", ans ? ans : n);



#ifdef debug
clock_t etime = clock();
printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif
return 0;
}



全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐