kmjp's blog

競技プログラミング参加記です

第四回 アルゴリズム実技検定 : M - 筆塗り

ここら辺はすんなり。
https://atcoder.jp/contests/past202010-open/tasks/past202010_m

問題

木を成す無向グラフが与えられる。
初期状態で、各点は色0で塗られている。

ここで以下のクエリを順次行う。

  • 2点(u,v)と色cが与えられる。パスu-v間の頂点を、色cで上書きする。

最終的に各点は何色になるか答えよ。

解法

マージテクを使い、各点が何回目のクエリで上書きされるかを列挙したうえで、一番最後のタイミングの色を採用しよう。
そのため、u-LCA(u,v)間と、v-LCA(u,v)間に彩色が追加・削除されるというイベントを追加し、DFSで葉から処理して行けばよい。

int N,Q;
vector<int> E[200005];
int P[21][200005],D[200005];

set<int> S[202020],del[202020];
int C[202020],ret[202020];
map<pair<int,int>,int> id;
void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
int getpar(int cur,int up) {
	int i;
	FOR(i,20) if(up&(1<<i)) cur=P[i][cur];
	return cur;
}

int lca(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return (aa==bb)?aa:P[0][aa];               // vertex
}

void dfs2(int cur,int pre=0) {
	FORR(e,E[cur]) if(e!=pre) {
		dfs2(e,cur);
		if(S[cur].size()<S[e].size()) swap(S[cur],S[e]);
		FORR(s,S[e]) S[cur].insert(s);
		S[e].clear();
		
	}
	FORR(d,del[cur]) S[cur].erase(d);
	
	if(S[cur].size()&&cur) {
		ret[id[{cur,pre}]]=C[*S[cur].rbegin()];
	}
	
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
		id[{x-1,y-1}]=id[{y-1,x-1}]=i;
	}
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];
	FOR(i,Q) {
		cin>>x>>y>>C[i];
		x--,y--;
		int lc=lca(x,y);
		S[x].insert(i);
		S[y].insert(i);
		del[lc].insert(i);
	}
	dfs2(0);
	FOR(i,N-1) cout<<ret[i]<<endl;
}

まとめ

マージテクもPASTの対象なのね。