Submission #2504886

---

Source Code Expand

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}

struct Seg {
    int ro[2];
    int in[2];
    int st[2];
    Seg(int) {
	ro[0] = in[0] = 0;
	ro[1] = in[1] = 1;
    }

    Seg() {
	in[0] = in[1] = ro[0] = ro[1] = 1<<29;
    }
    Seg inc(int init) const {
	Seg z;
	if (init) {
	    z.ro[1] = ro[1] + 2;
	    z.ro[0] = z.ro[1] + 1;
	    z.in[1] = in[0] + 1;
	    z.in[0] = z.in[1] + 1;
	    if (ro[0] == 0) {
		amin(z.ro[0], 0);
		amin(z.ro[1], 1);
		amin(z.in[0], 0);
		amin(z.in[1], 1);
	    }
	} else {
	    z.ro[1] = ro[0] + 2;
	    z.ro[0] = z.ro[1] + 1;
	    z.in[1] = in[1] + 1;
	    z.in[0] = z.in[1] + 1;
	}
	return z;
    }
};

Seg operator+(const Seg &x, const Seg &y) {
    Seg z;
    REP (a, 2) REP (b, 2) {
	int c = a^b;
	amin(z.ro[c], x.ro[a] + y.ro[b]);
	amin(z.in[c], x.ro[a] + y.in[b]);
	amin(z.in[c], x.in[a] + y.ro[b]);
    }

    REP (a, 2) {
	amin(z.ro[a], z.ro[a^1] + 1);
	amin(z.in[a], z.in[a^1] + 1);
    }
    return z;
}

const int MAXN = 100011;
int N;
VI G[MAXN];
char C[MAXN];

VI ord;
Seg ans[MAXN], up[MAXN], dw[MAXN];
vector<Seg> L[MAXN], R[MAXN];

void treeDP() {
    ord.clear(); ord.reserve(N);
    ord.push_back(0);
    REP (i_, N) {
	int v = ord[i_];
	EACH (e, G[v]) {
	    ord.push_back(*e);
	    G[*e].erase(remove(G[*e].begin(), G[*e].end(), v), G[*e].end()); // remove parent
	}
    }

    REP (i_, N) {
	int v = ord[N-1-i_];
	int m = G[v].size();
	L[v].assign(m+1, Seg());
	R[v].assign(m+1, Seg());
	L[v][0] = Seg(-1);
	R[v][m] = Seg(-1);
	REP (i, m)
	    L[v][i+1] = L[v][i] + up[G[v][i]];
	for (int i=m; i--; )
	    R[v][i] = up[G[v][i]] + R[v][i+1];
	up[v] = R[v][0].inc(C[v]);
    }

    dw[0] = Seg(-1);
    REP (i_, N) {
	int v = ord[i_];
	ans[v] = (R[v][0] + dw[v]); // when v == 0, dw[v] is an empty tree
	REP (i, G[v].size()) {
	    int w = G[v][i];
	    dw[w] = (R[v][i+1] + dw[v] + L[v][i]).inc(C[v]); // add v own
	}
    }
}

void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
    }

    scanf("%s", C);
    REP (i, N) C[i] = (C[i] == 'B');

    treeDP();

    int out = 1<<29;
    REP (i, N) {
	amin(out, ans[i].in[1-C[i]]);
    }

    printf("%d\n", out);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:120:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
                    ^
./Main.cpp:123:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &x, &y);
                       ^
./Main.cpp:129:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", C);
                   ^

Judge Result