Submission #2501491

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;

void dfs_ignore(int u, int p, vector<vector<int>>& G, vector<int>& a, vector<bool>& ignore) {
	ignore[u] = a[u];
	for (int v: G[u]) if (v != p) {
		dfs_ignore(v, u, G, a, ignore);
		if (!ignore[v]) ignore[u] = false;
	}
}

int maji = INT_MIN / 10;

void dfs_ma(int u, int p, vector<vector<int>>& G, vector<int>& a, vector<bool>& ignore, vector<int>& dp) {
	vector<int> unko = {0, 0};
	for (int v: G[u]) if (v != p && !ignore[v]) {
		dfs_ma(v, u, G, a, ignore, dp);
		unko.pb(dp[v]);
	}
	sort(unko.rbegin(), unko.rend());
	int x = a[u] ? 0 : 2;
	maji = max(maji, x + unko[0] + unko[1] + 1);
	dp[u] = x + unko[0];
}

int main() {
	int N; cin >> N;
	vector<vector<int>> G(N);
	rep(i, N - 1) {
		int u, v; scanf("%d%d", &u, &v), u--, v--;
		G[u].pb(v), G[v].pb(u);
	}
	string s; cin >> s;
	vector<int> a(N);
	rep(u, N) a[u] = (s[u] == 'B');
	int r = -1;
	rep(u, N) if (!a[u]) r = u;
	if (r == -1) {
		cout << 0 << endl;
		return 0;
	}
	vector<bool> ignore(N);
	dfs_ignore(r, -1, G, a, ignore);
	int ans = -1;
	rep(u, N) if (!ignore[u]) {
		ans += 2;
		int deg = 0;
		for (int v: G[u]) if (!ignore[v]) deg++;
		a[u] ^= deg % 2;
		ans += !a[u];
	}
	if (ans == 2) {
		cout << 1 << endl;
		return 0;
	}
	int ma = 1;
	vector<int> dp(N);
	dfs_ma(r, -1, G, a, ignore, dp);
	ma = max(ma, maji);
	cout << ans - ma << endl;
}

Submission Info

Compile Error

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

Judge Result