Submission #2502564

---

Source Code Expand

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
vector<int>pat[101010];
bool flag[101010];
bool isv[101010];
string str;
bool dfs(int node)
{
	flag[node] = true;
	bool r = (str[node] == 'W');
	for (int i = 0; i < pat[node].size(); i++)
	{
		int v = pat[node][i];
		if (flag[v])continue;
		r |= dfs(v);
	}
	return isv[node] = r;
}
int sc[101010];
int maxi = 0;
int calc(int node)
{
	flag[node] = true;
	int m1 = 0, m2 = 0;
	for (int i = 0; i < pat[node].size(); i++)
	{
		int v = pat[node][i];
		if (!isv[v])continue;
		if (flag[v])continue;
		int t = calc(v);
		if (m1 < t)m2 = m1, m1 = t;
		else if (m2 < t)m2 = t;
	}
	//printf("%d %d %d\n", node + 1, m1, m2);
	maxi = max(maxi, m1 + m2 + ((str[node] == 'W') ? 2 : 0));
	return m1 + ((str[node] == 'W') ? 2 : 0);
}
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num - 1; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	cin >> str;
	int rr = -1;
	for (int i = 0; i < num; i++)if (str[i] == 'W')rr = i;
	if (rr == -1)
	{
		printf("0\n");
		return 0;
	}
	dfs(rr);
	int cnt = 0;
	for (int i = 0; i < num; i++)cnt += isv[i];
	if (cnt == 1)
	{
		printf("1\n");
		return 0;
	}
	for (int i = 0; i < num; i++)
	{
		//if (isv[i])printf("%d\n", i + 1);
		for (int j = 0; j < pat[i].size(); j++)
		{
			if (isv[i] && isv[pat[i][j]])str[i] = 'W' + 'B' - str[i];
		}
	}
	//cout << str << endl;
	fill(flag, flag + num, false);
	calc(rr);
	int ans = cnt * 2 - 2;
	for (int i = 0; i < num; i++)if (isv[i] && str[i] == 'W')ans++;
	printf("%d\n", ans - maxi);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:45:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &num);
                   ^
./Main.cpp:49:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &za, &zb);
                          ^

Judge Result