yukicoder : No.1054 Union add query

これ★3.5でもいい気はするけど。
https://yukicoder.me/problems/no/1054

問題

初期状態で辺がなく、各頂点に数値0が設定された無向グラフがある。
以下のクエリに順次答えよ。

• 指定された2点u-vの間に辺を追加する
• 指定された点vと連結な点の数値に、wを加算する
• 指定された点vの現在値を答える

解法

Editorialとは違うけど、まぁ珍しくない解法。
まずクエリを1周し、辺追加クエリを処理しながら木構造を作る。

R(v)を、点vを含む連結成分の代表点とする。初期状態ではR(v)=vである。
今点v,wが非連結で、新たに点を追加する場合、新たな点uを設定して、u-R(v)とu-R(w)間に辺をはる。
また、R(v)=R(w)=uとする。
このようにすると、連結関係に基づく木ができる。

この木をオイラーツアーで探索しておこう。
クエリをもう1周するが、2番目のクエリがSubTreeへの数値加算とみなせるようになって、オイラーツアーの結果を用いてBITで処理できるようになる。

int N,Q;
int T[505050],A[505050],B[505050];
int cur[505050];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1500000> uf;
vector<int> E[1010101];
int nex;
int id;
int L[1010101],R[1010101];

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,21> bt;

void dfs(int cur) {
	if(L[cur]!=-1) return;
	L[cur]=id++;
	FORR(e,E[cur]) dfs(e);
	R[cur]=id;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cur[i]=i;
	nex=N;
	FOR(i,Q) {
		cin>>T[i]>>A[i]>>B[i];
		A[i]--;
		if(T[i]==1) {
			B[i]--;
			if(uf[A[i]]!=uf[B[i]]) {
				E[nex].push_back(cur[uf[A[i]]]);
				E[nex].push_back(cur[uf[B[i]]]);
				cur[uf[A[i]]]=cur[uf[B[i]]]=nex;
				uf(A[i],B[i]);
				nex++;
			}
		}
	}
	MINUS(L);
	uf.reinit();
	for(i=nex-1;i>=0;i--) dfs(i);
	FOR(i,N) cur[i]=i;
	nex=N;
	FOR(i,Q) {
		if(T[i]==1) {
			if(uf[A[i]]!=uf[B[i]]) {
				cur[uf[A[i]]]=cur[uf[B[i]]]=nex;
				uf(A[i],B[i]);
				nex++;
			}
		}
		else if(T[i]==2) {
			x=cur[uf[A[i]]];
			bt.add(L[x],B[i]);
			bt.add(R[x],-B[i]);
		}
		else {
			cout<<bt(L[A[i]])<<endl;
		}
	}
	
}

まとめ

難しくはないけどいろいろ使って面倒だしね。