Codeforces #722 Div1 : C. Trees of Tranquillity

Bに比べコードが長いな。
https://codeforces.com/contest/1528/problem/C

問題

2つのN頂点からなる根付き木が与えられる。
この木をもとに、以下のように新たなN頂点のグラフを作る。

2点u-v間に辺が張られる条件は、以下の両方を満たす場合である。

• 前者のグラフで、u-vが祖先と子孫の関係にある
• 後者のグラフで、u-vが祖先と子孫の関係にない

このグラフの最大クリークを求めよ。

解法

前者の条件より、最大クリークを成す頂点は、前者の木における1つの根からある頂点までのパス上の点の一部となる。

そこで以下のように処理する。
まず後者のグラフで、DFS順で番号を振りなおしておく。
次に前者のグラフをDFSでたどり、BITを使って祖先の頂点の(DFSで振りなおした)番号の個数を高速に求められるようにしておこう。

DFSをしながら、このBITに1加減算をしながら、総数が最大となるケースを求めたい。
ただし後者の条件より、後者のグラフで祖先・子孫の関係にある点が存在してはならない。
この時、祖先・子孫の関係にある点のいずれかを残すなら、後者の方が良い。（以後DFSの過程で再度後者の条件に反する可能性が減るため）

そこで、DFSをしながらBITに以下の条件で点を追加したり減らしたりしよう。

• すでに前者のグラフで祖先の頂点のうち、後者のグラフでSubTree内にある頂点があるなら、今見ている点は追加しない。
• 今見ている点は追加する場合、もし後者のグラフで祖先の頂点が存在するなら、それを消す。

int T;
int N;
int A[303030],B[303030];
vector<int> AE[303030],BE[303030];
int id;
int L[303030],R[303030],re[303030];
set<int> alive;
int num;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v; //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<19> st;

void dfs(int cur) {
	L[cur]=id++;
	re[L[cur]]=cur;
	FORR(e,BE[cur]) dfs(e);
	R[cur]=id;
}
int ma;

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,20> bt;

void dfs2(int cur) {
	
	
	bt.add(L[cur],1);
	int sub=bt(R[cur]-1)-bt(L[cur]);
	if(sub==0) num++;
	st.update(L[cur],R[cur]);
	//上を探す
	int x=-1,i;
	if(st.getval(0,L[cur])>=R[cur]) {
		x=0;
		for(i=20;i>=0;i--) if(x+(1<<i)<L[cur] && st.getval(x+(1<<i),L[cur])>=R[cur]) x+=1<<i;
		int t=re[x];
		sub=bt(R[t]-1)-bt(L[t]);
		if(sub==1) num--;
	}
	
	ma=max(ma,num);
	
	FORR(e,AE[cur]) dfs2(e);
	
	bt.add(L[cur],-1);
	sub=bt(R[cur]-1)-bt(L[cur]);
	if(sub==0) num--;
	st.update(L[cur],0);
	
	if(x!=-1) {
		int t=re[x];
		sub=bt(R[t]-1)-bt(L[t]);
		if(sub==0) num++;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d",&N);
		FOR(i,N) AE[i].clear(),BE[i].clear();
		
		for(i=1;i<N;i++) {
			scanf("%d",&A[i]);
			A[i]--;
			AE[A[i]].push_back(i);
		}
		for(i=1;i<N;i++) {
			scanf("%d",&B[i]);
			B[i]--;
			BE[B[i]].push_back(i);
		}
		id=0;
		dfs(0);
		
		ma=0;
		dfs2(0);
		
		cout<<ma<<endl;
	}
}

まとめ

これやってることはそんなに複雑じゃないんだけど、文字で書くの割とめんどいな。