Submission #2503413

---

Source Code Expand

#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=100000;

int n;
vector<int> adj[MAXN];
char col[MAXN];

bool alive[MAXN];
int deg[MAXN];
int q[MAXN],qhead,qtail;

bool gain[MAXN];

pair<ll,ll> dfspath(int at,int par) { // returns (longest path starting here,longest path in subtree)
	ll mxsofar=gain[at]?n:0;
	pair<ll,ll> ret=MP(mxsofar,mxsofar);
	REPSZ(i,adj[at]) {
		int to=adj[at][i]; if(to==par||!alive[to]) continue;
		pair<ll,ll> cur=dfspath(to,at);
		ll curpath=cur.first+1+(gain[at]?n:0);
		ret.first=max(ret.first,curpath);
		ret.second=max(ret.second,cur.second);
		ret.second=max(ret.second,mxsofar+cur.first+1);
		mxsofar=max(mxsofar,curpath);
	}
	return ret;
}

int solve() {
	bool anywhite=false; REP(i,n) if(col[i]=='W') anywhite=true; if(!anywhite) return 0;

	REP(i,n) alive[i]=true,deg[i]=SZ(adj[i]); qhead=qtail=0;
	REP(i,n) if(deg[i]==1&&col[i]=='B') alive[i]=false,q[qhead++]=i;
	while(qtail<qhead) {
		int at=q[qtail++];
		REPSZ(i,adj[at]) {
			int to=adj[at][i]; if(!alive[to]) continue;
			if(--deg[to]<=1&&col[to]=='B') alive[to]=false,q[qhead++]=to;
		}
	}
	REP(i,n) if(alive[i]&&deg[i]<=1) assert(col[i]=='W');
	REP(i,n) gain[i]=alive[i]&&(col[i]=='B'&&deg[i]%2==1||col[i]=='W'&&deg[i]%2==0);
	int numalive=0; REP(i,n) if(alive[i]) ++numalive; if(numalive==1) return 1;
	//printf("alive:"); REP(i,n) if(alive[i]) printf(" %d",i+1); puts("");
	//printf("gain:"); REP(i,n) if(gain[i]) printf(" %d",i+1); puts("");

	int root=-1; REP(i,n) if(alive[i]) { root=i; break; } assert(root!=-1);
	pair<ll,ll> longpath=dfspath(root,-1);
	int longedges=longpath.second%n,longgain=longpath.second/n;
	int degsum=0; REP(i,n) if(alive[i]) degsum+=deg[i];
	int gaincnt=0; REP(i,n) if(gain[i]) ++gaincnt;
	//printf("degsum=%d gaincnt=%d longedges=%d longgain=%d\n",degsum,gaincnt,longedges,longgain);
	return degsum+gaincnt-longedges-longgain+(longedges-1-longgain)+1;
}

void run() {
	scanf("%d",&n); REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); } REP(i,n) scanf(" %c",&col[i]);
	printf("%d\n",solve());
}

int main() {
	run();
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void run()’:
./Main.cpp:88:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); } REP(i,n) scanf(" %c",&col[i]);
                ^
./Main.cpp:88:59: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); } REP(i,n) scanf(" %c",&col[i]);
                                                           ^
./Main.cpp:88:129: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n); REP(i,n-1) { int a,b; scanf("%d%d",&a,&b); --a,--b; adj[a].PB(b); adj[b].PB(a); } REP(i,n) scanf(" %c",&col[i]);
                                                                              ...

Judge Result