Submission #2513100


Source Code Expand

/* --- author: dxm --- */
#include<bits/stdc++.h>
using namespace std;

#define INF 1e9
#define Inf 1e18
#define rep(i,n) for(int (i)=0;(i)<n;i++)
#define REP(i,n) for(int (i)=1;(i)<=n;i++)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define fst first
#define snd second
typedef long long ll;
inline void Fail(){printf("0");exit(0);}
inline void upd(ll &a,ll b){if(b<a)a=b;}

const int maxn=100005;
int n,col[maxn],son[maxn];
vector<int>edge[maxn];
ll dp[maxn][2][2][2],ans;
ll pre[maxn],suf[maxn];
char c[maxn];

void dfs(int x,int p,int sign){
	int sz=0;
	ll sum=0;
	rep(i,edge[x].size()){
		int y=edge[x][i];
		if(y==p)continue;
		dfs(y,x,sign&col[x]);
		if(dp[y][1][0][1]!=0)sum+=dp[y][0][0][1]+2,son[sz]=y,sz++;
	}
	if(!sz){
		rep(i,2)rep(j,2)rep(k,2){
			dp[x][i][j][k]=(col[x]+i)%2;
		} 
		goto end;
	}
//	cout<<x<<" "<<sz<<endl;
	pre[0]=sum-dp[son[0]][0][0][1]-2+dp[son[0]][1][1][1]+1;
	REP(i,sz-1)pre[i]=min(pre[i-1],sum-dp[son[i]][0][0][1]-2+dp[son[i]][1][1][1]+1);
	suf[sz-1]=sum-dp[son[sz-1]][0][0][1]-2+dp[son[sz-1]][1][1][1]+1;
	for(int i=sz-2;i>=0;i--)suf[i]=min(suf[i+1],sum-dp[son[i]][0][0][1]-2+dp[son[i]][1][1][1]+1);
	rep(i,2){
		dp[x][i][0][0]=Inf;
		rep(j,sz)upd(dp[x][i][0][0],sum-dp[son[j]][0][0][1]-2+dp[son[j]][0][0][0]+1);
		dp[x][i][0][0]+=(sz+col[x]+1+i)%2;
		dp[x][i][0][1]=sum+(sz+col[x]+i)%2;
		dp[x][i][1][0]=Inf;
		if(sz==1){
			if(i==col[x])dp[x][i][1][0]=dp[son[0]][1][1][0];
			else dp[x][i][1][0]=dp[son[0]][0][1][0]+2+(col[x]+sz+1+i)%2;
		}
		else{
			rep(j,sz){
				ll cur=min((!j?Inf:pre[j-1]),(j==sz-1?Inf:suf[j+1]))-dp[son[j]][0][0][1]-2;
				upd(dp[x][i][1][0],cur+dp[son[j]][0][0][0]+1+(sz+col[x]+1+i)%2);
				upd(dp[x][i][1][0],sum-dp[son[j]][0][0][1]-2+dp[son[j]][0][1][0]+2+(sz+col[x]+i)%2);
			}
		}
		dp[x][i][1][1]=Inf;
		rep(j,sz)upd(dp[x][i][1][1],sum-dp[son[j]][0][0][1]-2+dp[son[j]][1][1][1]+1);
		dp[x][i][1][1]+=(sz+col[x]+i)%2;
	}
	end:
	rep(i,2)rep(j,2){
		upd(dp[x][i][j][1],dp[x][i^1][j][1]+1);
	}
	if(sign){
		rep(i,2)rep(j,2)upd(ans,dp[x][1][i][j]);
	}
//	cout<<x<<" "<<dp[x][0][0][0]<<" "<<dp[x][0][0][1]<<" "<<dp[x][0][1][0]<<" "<<dp[x][0][1][1]<<endl;
//	cout<<x<<" "<<dp[x][1][0][0]<<" "<<dp[x][1][0][1]<<" "<<dp[x][1][1][0]<<" "<<dp[x][1][1][1]<<endl;
}

int main(){
//	freopen("F.in","r",stdin);
//	freopen("F.out","w",stdout);
	scanf("%d",&n);
	rep(i,n-1){
		int u,v;
		scanf("%d%d",&u,&v);
		u--;v--;
		edge[u].pb(v);
		edge[v].pb(u);
	}
	scanf("%s",c);
	rep(i,n)col[i]=c[i]=='W'?0:1;
	ans=Inf;
	dfs(0,-1,1);
	printf("%lld\n",ans);
	return 0;
}

/*
Input:
-----------------
Output:
*/

Submission Info

Submission Time
Task F - Monochrome Cat
User little_waxberry
Language C++ (GCC 5.4.1)
Score 0
Code Size 2678 Byte
Status WA
Exec Time 55 ms
Memory 23296 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:80:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:83: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:88:15: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",c);
               ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 800
Status
AC × 4
AC × 59
WA × 59
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt, 1_042.txt, 1_043.txt, 1_044.txt, 1_045.txt, 1_046.txt, 1_047.txt, 1_048.txt, 1_049.txt, 1_050.txt, 1_051.txt, 1_052.txt, 1_053.txt, 1_054.txt, 1_055.txt, 1_056.txt, 1_057.txt, 1_058.txt, 1_059.txt, 1_060.txt, 1_061.txt, 1_062.txt, 1_063.txt, 1_064.txt, 1_065.txt, 1_066.txt, 1_067.txt, 1_068.txt, 1_069.txt, 1_070.txt, 1_071.txt, 1_072.txt, 1_073.txt, 1_074.txt, 1_075.txt, 1_076.txt, 1_077.txt, 1_078.txt, 1_079.txt, 1_080.txt, 1_081.txt, 1_082.txt, 1_083.txt, 1_084.txt, 1_085.txt, 1_086.txt, 1_087.txt, 1_088.txt, 1_089.txt, 1_090.txt, 1_091.txt, 1_092.txt, 1_093.txt, 1_094.txt, 1_095.txt, 1_096.txt, 1_097.txt, 1_098.txt, 1_099.txt, 1_100.txt, 1_101.txt, 1_102.txt, 1_103.txt, 1_104.txt, 1_105.txt, 1_106.txt, 1_107.txt, 1_108.txt, 1_109.txt, 1_110.txt, 1_111.txt, 1_112.txt, 1_113.txt, 1_114.txt, 1_115.txt, 1_116.txt
Case Name Status Exec Time Memory
0_000.txt AC 2 ms 4352 KB
0_001.txt AC 2 ms 4352 KB
0_002.txt AC 2 ms 4352 KB
0_003.txt AC 2 ms 4352 KB
1_003.txt AC 2 ms 4352 KB
1_004.txt AC 2 ms 4352 KB
1_005.txt AC 2 ms 4352 KB
1_006.txt AC 2 ms 4352 KB
1_007.txt AC 2 ms 4352 KB
1_008.txt AC 2 ms 4352 KB
1_009.txt AC 2 ms 4352 KB
1_010.txt WA 2 ms 4352 KB
1_011.txt AC 2 ms 4352 KB
1_012.txt AC 2 ms 4352 KB
1_013.txt WA 2 ms 4352 KB
1_014.txt AC 2 ms 4352 KB
1_015.txt AC 2 ms 4352 KB
1_016.txt AC 2 ms 4352 KB
1_017.txt AC 2 ms 4352 KB
1_018.txt WA 2 ms 4352 KB
1_019.txt AC 2 ms 4352 KB
1_020.txt AC 2 ms 4352 KB
1_021.txt AC 2 ms 4352 KB
1_022.txt WA 2 ms 4352 KB
1_023.txt AC 2 ms 4352 KB
1_024.txt WA 2 ms 4352 KB
1_025.txt AC 2 ms 4352 KB
1_026.txt AC 2 ms 4352 KB
1_027.txt AC 2 ms 4352 KB
1_028.txt WA 2 ms 4352 KB
1_029.txt AC 2 ms 4352 KB
1_030.txt WA 2 ms 4352 KB
1_031.txt AC 2 ms 4352 KB
1_032.txt AC 2 ms 4352 KB
1_033.txt AC 2 ms 4352 KB
1_034.txt AC 2 ms 4352 KB
1_035.txt AC 2 ms 4352 KB
1_036.txt WA 2 ms 4352 KB
1_037.txt AC 2 ms 4352 KB
1_038.txt WA 2 ms 4352 KB
1_039.txt WA 2 ms 4352 KB
1_040.txt AC 2 ms 4352 KB
1_041.txt AC 2 ms 4352 KB
1_042.txt AC 2 ms 4352 KB
1_043.txt AC 2 ms 4352 KB
1_044.txt AC 2 ms 4352 KB
1_045.txt WA 18 ms 11008 KB
1_046.txt WA 22 ms 14976 KB
1_047.txt AC 45 ms 19840 KB
1_048.txt WA 35 ms 18688 KB
1_049.txt WA 35 ms 16640 KB
1_050.txt WA 31 ms 16256 KB
1_051.txt AC 27 ms 13304 KB
1_052.txt AC 8 ms 7680 KB
1_053.txt AC 27 ms 12280 KB
1_054.txt WA 12 ms 8188 KB
1_055.txt AC 27 ms 13304 KB
1_056.txt AC 16 ms 10748 KB
1_057.txt WA 3 ms 4608 KB
1_058.txt WA 21 ms 12032 KB
1_059.txt AC 17 ms 9088 KB
1_060.txt WA 32 ms 13952 KB
1_061.txt WA 38 ms 14848 KB
1_062.txt WA 21 ms 12544 KB
1_063.txt WA 26 ms 11776 KB
1_064.txt WA 18 ms 10752 KB
1_065.txt AC 4 ms 4992 KB
1_066.txt WA 30 ms 11900 KB
1_067.txt WA 9 ms 7680 KB
1_068.txt WA 21 ms 11008 KB
1_069.txt WA 13 ms 7808 KB
1_070.txt WA 21 ms 10624 KB
1_071.txt AC 35 ms 11904 KB
1_072.txt WA 22 ms 10752 KB
1_073.txt WA 6 ms 7168 KB
1_074.txt WA 4 ms 4992 KB
1_075.txt WA 20 ms 10496 KB
1_076.txt WA 41 ms 12416 KB
1_077.txt AC 33 ms 11776 KB
1_078.txt WA 13 ms 7936 KB
1_079.txt WA 20 ms 10368 KB
1_080.txt WA 21 ms 10624 KB
1_081.txt WA 47 ms 18432 KB
1_082.txt WA 48 ms 18816 KB
1_083.txt AC 48 ms 23296 KB
1_084.txt WA 46 ms 18944 KB
1_085.txt WA 49 ms 21760 KB
1_086.txt WA 55 ms 22144 KB
1_087.txt AC 37 ms 14840 KB
1_088.txt AC 34 ms 13816 KB
1_089.txt AC 32 ms 12792 KB
1_090.txt WA 37 ms 12792 KB
1_091.txt AC 36 ms 14840 KB
1_092.txt AC 32 ms 12792 KB
1_093.txt WA 46 ms 15744 KB
1_094.txt WA 47 ms 17792 KB
1_095.txt AC 43 ms 16384 KB
1_096.txt WA 44 ms 17408 KB
1_097.txt WA 45 ms 16640 KB
1_098.txt WA 46 ms 17152 KB
1_099.txt WA 40 ms 13692 KB
1_100.txt WA 39 ms 13308 KB
1_101.txt AC 37 ms 12668 KB
1_102.txt WA 37 ms 12668 KB
1_103.txt WA 40 ms 13692 KB
1_104.txt AC 38 ms 13052 KB
1_105.txt WA 43 ms 12544 KB
1_106.txt WA 42 ms 12544 KB
1_107.txt AC 42 ms 12544 KB
1_108.txt WA 42 ms 12544 KB
1_109.txt AC 46 ms 12544 KB
1_110.txt WA 42 ms 12544 KB
1_111.txt WA 50 ms 12544 KB
1_112.txt WA 43 ms 12544 KB
1_113.txt AC 41 ms 12544 KB
1_114.txt WA 42 ms 12544 KB
1_115.txt AC 42 ms 12544 KB
1_116.txt WA 42 ms 12544 KB