Submission #8418523

---

Source Code Expand

#include<stdio.h>
#include<queue>
using namespace std;
int head[131072],last[262144],to[262144],cnt=0;
int deg[131072];
void add(int u,int v)
{
	cnt++;
	last[cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	deg[u]++;
}
char s[131072];
queue<int> q;
int tp[131072];
int dis[131072];
void dfs(int u,int f,int d)
{
	d+=tp[u];
	dis[u]=d;
	for(int i=head[u];i;i=last[i])
	{
		int v=to[i];
		if(v==f)
		{
			continue;
		}
		if(deg[v]==0)
		{
			continue;
		}
		dfs(v,u,d);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u);
	}
	scanf("%s",s+1);
	int numw=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='W')
		{
			numw++;
		}
	}
	if(numw<=1)
	{
		printf("%d\n",numw);
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='B'&&deg[i]==1)
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		deg[u]=0;
		for(int i=head[u];i;i=last[i])
		{
			int v=to[i];
			if(deg[v])
			{
				deg[v]--;
				if(deg[v]==1&&s[v]=='B')
				{
					q.push(v);
				}
			}
		}
	}
	int ans=-2;
	for(int i=1;i<=n;i++)
	{
		if(deg[i])
		{
			ans+=2;
			tp[i]=((deg[i]+(s[i]=='W'))&1);
			ans+=tp[i];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(deg[i]==1)
		{
			dfs(i,0,0);
			break;
		}
	}
	int u=0,d=-1;
	for(int i=1;i<=n;i++)
	{
		if(deg[i]==1)
		{
			if(dis[i]>d)
			{
				u=i;
				d=dis[i];
			}
		}
	}
	dfs(u,0,0);
	u=0,d=-1;
	for(int i=1;i<=n;i++)
	{
		if(deg[i]==1)
		{
			if(dis[i]>d)
			{
				u=i;
				d=dis[i];
			}
		}
	}
	printf("%d\n",ans-d-d);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:39:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:43:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
                      ^
./Main.cpp:47:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
                 ^

Judge Result