Submission #2505443

---

Source Code Expand

#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

int ans;
char c[100001];
int a[100000];
set <int> s[100000];

int dfs(int x, int y) {
    int p = 0, q = 0;
    set <int>::iterator it;
    
    for (it = s[x].begin(); it != s[x].end(); it++) {
        int nx = *it;
        
        if (nx != y) {
            int r = dfs(nx, x);
            
            if (r > p) {
                q = p;
                p = r;
            } else if (r > q) {
                q = r;
            }
        }
    }
    
    p += a[x];
    ans = max(ans, p + q);
    return p;
}

int main() {
    int n, num, i;
    queue <int> q;
    
    scanf("%d", &n);
    
    for (i = 0; i < n - 1; i++) {
        int x, y;
        
        scanf("%d %d", &x, &y);
        
        x--;
        y--;
        
        s[x].insert(y);
        s[y].insert(x);
    }
    
    scanf("%s", c);
    
    num = n;
    
    for (i = 0; i < n; i++) {
        if (c[i] == 'B' && s[i].size() <= 1) q.push(i);
    }
    
    while (!q.empty()) {
        int x = q.front(), y;
        
        q.pop();
        
        if (s[x].size() == 0) break;
        
        y = *s[x].begin();
        
        num--;
        s[x].erase(y);
        s[y].erase(x);
        
        if (c[y] == 'B' && s[y].size() <= 1) q.push(y);
    }
    
    if (num <= 1) {
        for (i = 0; i < n; i++) {
            if (c[i] == 'W') ans++;
        }
        
        printf("%d\n", ans);
    } else {
        int p = -1;
        
        num = (num - 1) * 2;
        
        for (i = 0; i < n; i++) {
            if (s[i].size() == 0) continue;
            if (p == -1) p = i;
            
            if (c[i] == 'W') a[i] = 1;
            a[i] += s[i].size();
            a[i] %= 2;
            
            num += a[i];
        }
        
        dfs(p, -1);
        
        printf("%d\n", num - ans * 2);
    }
    
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:46:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &y);
                               ^
./Main.cpp:55:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", c);
                   ^

Judge Result