Codeforces #848 : Div2 E. The Tree Has Fallen!

だいぶコード量が増えてしまった。
https://codeforces.com/contest/1778/problem/E

問題

木を成す無向グラフが与えられる。
各点には非負整数値が設定されている。

以下のクエリに答えよ。

• 根頂点Rと、点Vが指定される。VのSubtree内の頂点のsubsetを選ぶとき、その点に設定された値のxorの最大値を求めよ。

解法

前処理として、各Subtreeにおける整数値群をbitvectorとみなしたときの基底ベクトルを全方位木DPで求めておこう。
あとはクエリ毎に基底ベクトルのbitwise-orを答えればよい。

int T;
int N;
vector<int> E[202020],LB[202020];
int A[202020];
int L[202020],R[202020];
vector<int> B[202020],P[202020];
vector<vector<int>> BL[202020];
vector<vector<int>> BR[202020];
int id;

void dfs(int cur,int pre) {
	L[cur]=id++;
	int i;
	FOR(i,E[cur].size()) {
		if(E[cur][i]==pre) {
			E[cur].erase(E[cur].begin()+i);
			break;
		}
	}
	BL[cur]={{}};
	BR[cur]={{}};
	LB[cur].clear();
	FORR(e,E[cur]) {
		dfs(e,cur);
		LB[cur].push_back(L[e]);
		BL[cur].push_back(BL[cur].back());
		FORR(b,B[e]) {
			int v=b;
			FORR(t,BL[cur].back()) v=min(v,t^v);
			if(v) BL[cur].back().push_back(v);
		}
	}
	R[cur]=id;
	reverse(ALL(E[cur]));
	FORR(e,E[cur]) {
		BR[cur].push_back(BR[cur].back());
		FORR(b,B[e]) {
			int v=b;
			FORR(t,BR[cur].back()) v=min(v,t^v);
			if(v) BR[cur].back().push_back(v);
		}
	}
	B[cur]=BL[cur].back();
	int v=A[cur];
	FORR(t,B[cur]) v=min(v,t^v);
	if(v) B[cur].push_back(v);
	
	reverse(ALL(E[cur]));
	reverse(ALL(BR[cur]));
}

vector<int> merge(vector<int> p2,int v,vector<int> A,vector<int> B) {
	FORR(p,p2) v=min(v,v^p);
	if(v) p2.push_back(v);
	FORR(b,A) {
		int v=b;
		FORR(p,p2) v=min(v,v^p);
		if(v) p2.push_back(v);
	}
	FORR(b,B) {
		int v=b;
		FORR(p,p2) v=min(v,v^p);
		if(v) p2.push_back(v);
	}
	return p2;
}

void dfs2(int cur,vector<int> par) {
	P[cur]=par;
	int i;
	FOR(i,E[cur].size()) {
		vector<int> p2=merge(par,A[cur],BL[cur][i],BR[cur][i+1]);
		dfs2(E[cur][i],p2);
	}
	
}

int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
			E[i].clear();
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		id=0;
		dfs(0,0);
		dfs2(0,vector<int>());
		cin>>Q;
		while(Q--) {
			int root,V;
			cin>>root>>V;
			root--,V--;
			int ret=0;
			if(root==V) {
				vector<int> p2=merge(P[V],A[V],B[V],B[V]);
				FORR(b,p2) ret=max(ret,ret^b);
			}
			else if(L[root]<L[V]||L[root]>=R[V]) {
				FORR(b,B[V]) ret=max(ret,ret^b);
			}
			else {
				i=lower_bound(ALL(LB[V]),L[root]+1)-LB[V].begin()-1;
				vector<int> p2=merge(P[V],A[V],BL[V][i],BR[V][i+1]);
				FORR(b,p2) ret=max(ret,ret^b);
				
			}
			cout<<ret<<endl;
		}
	}
	
}

まとめ

やることは自明だけど割とめんどい。