Codeforces #872 : Div1 C. LuoTianyi and XOR-Tree

コードは短め。
https://codeforces.com/contest/1824/problem/C

問題

根付き木が与えられる。
各点には整数値が設定されている。
いくつかの点の設定値を変更し、根頂点から葉へのパス上の設定値のxorが0となるようにしたい。
最小何個の点を0にすべきか。

解法

SubTree内の葉までのパスのうち、最多出現のものを0となるように、今いる点の値を設定する、という作業を繰り返していこう。

int N;
int A[202020];
vector<int> E[202020];
map<int,int> T[202020];
int ret;

void dfs(int cur,int pre) {
	int ma=1;
	if(cur&&E[cur].size()==1) {
		T[cur][A[cur]]=1;
	}
	else {
		FORR(e,E[cur]) if(e!=pre) {
			A[e]^=A[cur];
			dfs(e,cur);
			if(T[cur].size()<T[e].size()) swap(T[cur],T[e]);
			FORR2(a,b,T[e]) ma=max(ma,T[cur][a]+=b);
		}
		ret+=E[cur].size()-(cur!=0)-ma;
		if(ma>1) {
			T[N].clear();
			FORR2(a,b,T[cur]) if(b==ma) T[N][a]=1;
			swap(T[cur],T[N]);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,0);
	cout<<ret+(T[0].count(0)==0)<<endl;
	
}

まとめ

これなんで1750ptなんだろ。