AtCoder ABC #295 : G - Minimum Reachable City

不参加でした。
https://atcoder.jp/contests/abc295/tasks/abc295_g

問題

N頂点の有向根付き木が与えられる。
初期状態では、有向辺は番号の小さい方から大きい方に張られている。

以下のクエリに順次答えよ。

• 有効辺を追加する。この辺は、元の根付き木で子孫から祖先に向かう方向に張られる。
• 頂点番号が指定されるので、そこから辺に沿って遷移可能な頂点番号の最小値を求めよ。

解法

まず頂点をDFS訪問順に並べ替え、区間最小値を取るSegTreeで、各頂点から遷移可能な最小値を管理しよう。

• 前者のクエリに対しては、SegTreeを1点更新する。
• 後者のクエリに対しては、SegTreeを使いSubTree内から遷移できる最小番号をたどる、という作業を可能な限り繰り返す。またその結果に応じてSegTreeを更新する。

ということを繰り返して処理できる。

int N,Q;
int P[202020];
vector<int> E[202020];
int L[202020],R[202020];
int id;

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1<<20;
	V comp(V l,V r){ return min(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]=comp(v,val[entry]); //上書きかチェック
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;

void dfs(int cur) {
	L[cur]=id++;
	st.update(L[cur],cur);
	FORR(e,E[cur]) dfs(e);
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>P[i+1];
		P[i+1]--;
		E[P[i+1]].push_back(i+1);
	}
	dfs(0);
	
	cin>>Q;
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			x--,y--;
			st.update(L[x],y);
		}
		else {
			cin>>x;
			x=y=x-1;
			while(1) {
				k=st.getval(L[y],R[y]);
				if(k==y) break;
				y=k;
			}
			st.update(L[x],y);
			cout<<y+1<<endl;
		}
	}
}

まとめ

Union-Findでもできるのね…。