Submission #2502523

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef complex<double> point;
#define mapii map<int, int>
#define debug(a) cout << #a << ": " << a << endl
#define debuga1(a, l, r) fto(i, l, r) cout << a[i] << " "; cout << endl
#define fdto(i, r, l) for(int i = (r); i >= (l); --i)
#define fto(i, l, r) for(int i = (l); i <= (r); ++i)
#define forit(it, var) for(__typeof(var.begin()) it = var.begin(); it != var.end(); it++)
#define forrit(rit, var) for(__typeof(var.rbegin()) rit = var.rbegin(); rit != var.rend(); rit++)
#define ii pair<int, int>
#define iii pair<int, ii>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define maxN 100005
#define MOD 1000
#define oo 1000000007
#define sz(a) (int)a.size()

const double PI = acos(-1.0);

double fRand(double fMin, double fMax)
{
    double f = (double)rand() / RAND_MAX;
    return fMin + f * (fMax - fMin);
}

template <class T>
T min(T a, T b, T c) {
    return min(a, min(b, c));
}

template <class T>
T max(T a, T b, T c) {
    return max(a, max(b, c));
}

int n, root, color[maxN], dp[2][maxN], maxPath, ans;
bool marked[maxN];
vector<int> g[maxN];
char s[maxN];

void DFS1(int u, int p) {
    marked[u] = (color[u] == 0);
    for(int v: g[u]) {
        if (v == p) continue;
        DFS1(v, u);
        marked[u] |= marked[v];
    }
}

void Solve(int u, int p) {
    int x = (color[u] == 0) ? 2 : 0;
    for(int v: g[u]) {
        if (!marked[v] || v == p) continue;
        ans += 2;
        Solve(v, u);
        if (dp[0][v]+x > dp[0][u]) {
            dp[1][u] = dp[0][u];
            dp[0][u] = dp[0][v]+x;
        } else if (dp[0][v]+x > dp[1][u]) {
            dp[1][u] = dp[0][v]+x;
        }
    }

    maxPath = max(maxPath, dp[0][u] + dp[1][u] - x);

}

int main () {
    scanf("%d", &n);
    fto(i, 1, n-1) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].pb(v); g[v].pb(u);
    }
    scanf("%s", s);
    fto(u, 1, n) color[u] = (s[u-1] == 'B');

    fto(u, 1, n) {
        if (color[u] == 0) {root = u; break;}
    }

    if (root == 0) {
        puts("0");
        return 0;
    }

    DFS1(root, -1);

    fto(u, 1, n) {
        if (marked[u]) {
            for(int v: g[u])
                if (marked[v]) color[u] ^= 1;
            ans += (color[u] == 0);
        }
    }

    Solve(root, -1);

    ans -= maxPath;
    printf("%d", ans);


    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
./Main.cpp:79:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &u, &v);
                              ^
./Main.cpp:82:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
                   ^

Judge Result