Submission #3390621

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <bitset>
#include <stack>
#include <deque>
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const int MAXN = 123456;
const int NEG = -MAXN;
vector<int> G[MAXN], nG[MAXN];
int type[MAXN], s, t, dis;

bool dfs(int cur, int par) {
     bool OK = type[cur] ? 1 : 0;
     for (auto i : G[cur]) {
         if (i != par && !dfs(i, cur)) {
            nG[cur].push_back(i);
            nG[i].push_back(cur);
            OK = 0;
         }
     }
     return OK;
}

void dfs2(int cur, int par, int cost) {
    if (cost >= dis) {
       dis = cost;
       if (!t) s = cur;
       else t = cur;
    }
    int deg = (int)nG[cur].size();
    if (deg == 1 && nG[cur][0] == par) {
       // printf("cur = %d cost = %d\n", cur, cost);
       return;
    }
    int offset = 0;
    deg = (deg - 1) % 2;
    if (deg ^ type[cur]) offset = 1;
    else offset = -1;
    // printf("cur = %d off = %d cost = %d deg = %d type = %d\n", cur, offset, cost, deg, type[cur]);
    for (auto i : nG[cur]) {
        if (i != par) {
           dfs2(i, cur, cost + 1 + offset);
        }
    }
}

int main() {
    int N;
    // freopen("1_064.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int root = 0;
    for (int i = 1; i <= N; i++) {
        char c;
        scanf(" %c", &c);
        if (c == 'W') {
           type[i] = 0;
           root = i;
        } else {
           type[i] = 1;
        }
    }
    if (!root) return !printf("0\n");
    dfs(root, root);
    dfs2(root, root, 0);
    dis = 0;
    dfs2(s, s, 0);
    // if (!nG[root].size()) return !printf("1\n");
    int sum = 0;
    for (int i = 1; i <= N; i++) {
        int deg = (int)nG[i].size();
        sum += deg;
        deg %= 2;
        if (!(deg ^ type[i])) sum++;
    }
    // printf("sum = %d dis = %d\n", sum, dis);
    printf("%d\n", sum - dis);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:61:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:64: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:71:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &c);
                         ^

Judge Result