JOIOC13 Synchronization

문제

https://oj.uz/problem/view/JOI13_synchronization

문제 보기 - 동기화 (JOI13_synchronization) :: oj.uz

트리에서 처음에는 각 노드가 자기 자신만을 들고 있고, 각 시간마다 간선이 연결되거나 끊어지거나 한다. 또한, 간선이 연결되어 있으면 각 노드의 집합은 연결된 노드들의 합집합이 된다. 이때 모든 업데이트가 끝난 후의 집합의 크기를 출력해야 한다.

 

풀이

일단 가장 먼저 해야 하는 관찰은 각 집합은 트리 상에서의 하나의 연결된 컴포넌트를 구성한다는 것이다. 이는 직관적으로도 자명하지만, 증명을 하자면 u가 v를 집합에 갖고 있다 하자. 그렇다면 u에서 v로의 경로에 있는 w를 생각했을 때 u가 v를 갖게 되는 최초의 순간에는 u와 w, w와 v를 갖고 있는 어떠한 노드 p 모두 연결되어 있을 것이다. 그렇다면 p에 있던 v가 u로 오는 과정에서 w도 지나기 때문에 무조건 w도 포함된다.

 

이 관찰의 증명 과정처럼 u집합이 v를 포함하고 있는가? 의 관점으로만 생각해 보자. u집합에 v가 포함되어 있는지 어떻게 알 수 있을까? 두가지 관점으로 생각해 볼 수 있다. 일단 u와 v사이의 엣지들만 관련이 있음은 당연하다.

1. v가 u로 온다고 생각하자. 그렇다면 각 노드별로 이 노드가 v를 갖게 되는 최소 시간 t1을 저장한다면 v에서 t1은 0, 다음은 t1에서 다음 노드로 넘어갈 때 타는 간선이 켜지는 t1이상의 최소시간, 이렇게 계속 반복해주면 된다.

2. u가 v로 온다고 생각하자. 그렇다면 이번엔 거꾸로 u에 도착하기 위한 최대시간 t2를 생각하고, u에서 t2=INF, 다음은 t2에서 다음 노드로 넘어갈 때 타는 간선이 켜지는 t2이하의 최대 시간, 이렇게 반복해 주면 된다.

 

이러한 생각을 통해서 $O((N+M)log^3N)$ 정도의 풀이를 유도해 낼 수 있다. 사실 이 풀이와 유사한 풀이가 공식 슬라이드에 실려 있다.

일단 Centroid Decomposition 을 한다. 그러면 각 단계에서 centroid 를 기준으로 여러 개의 서브트리로 분할 될 것이다. 분할정복을 하기 위해서 어떤 노드 u의 서브트리(centroid에 의해 분할되지 않은) 에 포함되지 않은 다른 정점들이 내 집합에 포함될 수 있는지 여부를 생각해 주기만 하면 된다. 여기서 다른 정점을 v라 한다면 v가 u까지 흘러오기 위해서는 무조건 centroid 를 지나야 하니, 크게 경로를 다음의 2개로 쪼갤 수 있다.

1. v가 centroid까지 온다.

2. centroid 에서 u까지 간다. == u에서 centroid 까지 간다.

이는 위에서 언급한 2가지 상황과 같은 상황이다. 이제 위에서 언급했던 시간의 전이 과정만 빠르게 처리해 줄 수 있으면 된다.

 

일단 여기서 내가 생각한 풀이는 2가지 정도 되는데, 첫번째 풀이는 1~M까지의 타임라인에 대해 이 시간까지 올 수 있는 정점의 수를 관리하는 것이다. 리프에서부터 루트로 올라갈 때마다 그 간선의 공백에 해당하는 시간의 점들이 오른쪽으로 shift되고, 만약 어떤 같은 시간에 여러개의 정점이 속한다면 이는 이후에도 계속 같이 움직인다. 이 과정은 Union-Find + Small to Large를 이용하면 계산할 수 있을 것이다. 하지만 단순히 이 타임라인을 배열로 관리하면 문제가 발생하니 결국 segment tree까지 사용해야 해서 $O(log^2N)$이 나온다. 이 풀이는 구현을 하지는 않았다.

두번째 풀이는 HLD를 이용한다. 시간이 지날 때마다 각 정점들은 루트로만 움직여도 상관이 없다는 것을 알 수 있다. 결국 모두의 목표는 루트인 센트로이드까지의 도달 시간을 최소화하는 것이기 때문에 그렇다. 따라서 이제 간선들이 on/off 가 되었을 때 도달 가능한 가장 높은 노드를 빠르게 찾아줄 수 있으면 된다. 이 과정은 HLD를 하고 각 체인에 대한 set을 하나씩 관리하면 되고, 이 과정은 트리와 쿼리 3과 매우 비슷하다. https://www.acmicpc.net/problem/13512

2번째 전이의 경우 그저 시간을 뒤집고 똑같이 해주면 된다. 이를 구현하면 약 5000byte정도의 코드가 나오지만, set을 이용한 큰 상수가 붙은 약 8억 정도의 계산량을 견디지 못하고 TLE를 받는다.

 

사실 정해는 위의 Centroid Decomposition의 풀이와는 거의 상관도 없고 의외로 매우 간단하다. 하지만 저 과정을 생각함으로서 얻을 수 있는 다양한 관찰과 고찰들로 인해 나는 정해에 도달할 수 있었기에 써 놓았다.

 

이제 정해를 보자. 지금 이 문제가 어려운 이유가 뭘까? 만약 간선 끊는것이 없었으면 그냥 너무나도 쉬운 Union-Find 문제이다. 또, 만약 두 집합이 겹치는 부분만 없었어도 그냥 각 집합 크기를 더해주면 된다. 따라서, 이 교집합 부분만 잘 처리해주면 될 듯 한다. 어떻게 처리해야할까?

어떠한 간선 e가 끊겼다고 하자. 그 순간 e로 연결된 u, v는 어떠한 교집합을 가질 것이다. 그렇다면 e가 연결되기 전까지, u, v의 교집합이 과연 바뀔까? u와 v의 교집합에 어떠한 정점 w가 추가되었다고 하자. w가 추가된다는 말은 w에서 u까지의 경로, w에서 v까지의 경로가 다 존재하고, u와 v사이의 e가 존재하기 때문에 u, v 사이에 사이클이 존재해 모순이다.

그렇다면, 이 교집합 정보를 간선에다가 써 놓고, 간선이 다시 만들어질때마다 업데이트만 해주면 되지 않을까?

 

이제 간선이 추가될 때마다 u의 크기+v의 크기-간선의 교집합 크기로 u에 연결된 정점들과 v에 연결된 정점들의 크기 정보만 수정해주면 된다. 아직 이 과정이 오래 걸린다. 연결된 집합의 모든 정점에 저 연산을 해주기에는 좀 오래 걸린다. 이제 이를 위해 마지막 한가지 생각만 해주면 된다. 연결된 집합의 가장 꼭대기를 그 집합의 대표라고 생각하고, 그 루트에만 업데이트와 쿼리를 날려주자! 그 대표인 루트를 잡는 과정은 위에서 언급한 트리와 쿼리 3풀이와 같고, 이제 정점에 업데이트, 간선에 업데이트 과정만 해주면 된다. 트리와 쿼리 3을 푸는데는 HLD + set / Euler tour segment tree + set풀이 등이 존재하니 이를 적당히 활용해서 $O(Mlog^2N)$의 풀이를 구현하면 된다.

 

여담 : 더 빠른 풀이도 존재하는 것으로 알고 있지만, 이 문제에 거의 2일정도를 소비해서 더 이상 생각할 겨를이 없다...

 

시간 복잡도 : $O(Mlog^2N)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXM = 1e5;

int N, M, Q, P[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
vector<int> adj[MAXN+10];

int A[MAXN+10], B[MAXN+10];
int S[MAXN+10], E[MAXN+10], idx[MAXN+10], cnt;

void dfs(int now, int bef)
{
	S[now]=++cnt;
	idx[cnt]=now;
	for(auto &nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs(nxt, now);
	}
	E[now]=cnt;
}

struct priority_set
{
	priority_queue<int> PQ1, PQ2;
	void push(int x) { PQ1.push(x); }
	void pop(int x) { PQ2.push(x); }
	int top()
	{
		while(!PQ1.empty() && !PQ2.empty() && PQ1.top()==PQ2.top()) PQ1.pop(), PQ2.pop();
		if(PQ1.empty()) return -1;
		return PQ1.top();
	}
};

priority_set tree[MAXN*4+10];

void update1(int node, int tl, int tr, int l, int r, int v)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		tree[node].push(v);
		return;
	}
	int mid=tl+tr>>1;
	update1(node*2, tl, mid, l, r, v);
	update1(node*2+1, mid+1, tr, l, r, v);
}

void update2(int node, int tl, int tr, int l, int r, int v)
{
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		tree[node].pop(v);
		return;
	}
	int mid=tl+tr>>1;
	update2(node*2, tl, mid, l, r, v);
	update2(node*2+1, mid+1, tr, l, r, v);
}

int query(int node, int tl, int tr, int p)
{
	if(tl==tr) return tree[node].top();
	int mid=tl+tr>>1;
	if(p<=mid) return max(query(node*2, tl, mid, p), tree[node].top());
	else return max(query(node*2+1, mid+1, tr, p), tree[node].top());
}

void push(int x) { update1(1, 1, N, S[x], E[x], S[x]); }
void pop(int x) { update2(1, 1, N, S[x], E[x], S[x]); }
int query(int x) { return idx[query(1, 1, N, S[x])]; }

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &Q);
	for(i=1; i<N; i++)
	{
		scanf("%d%d", &X[i], &Y[i]);
		adj[X[i]].push_back(Y[i]);
		adj[Y[i]].push_back(X[i]);
	}

	dfs(1, 0);
	for(i=1; i<=N; i++) push(i), A[i]=1;
	for(i=1; i<N; i++) if(S[X[i]]<S[Y[i]]) swap(X[i], Y[i]);

	while(M--)
	{
		int e;
		scanf("%d", &e);
		if(P[e]==0)
		{
			int v=query(Y[e]), u=X[e];
			A[v]+=A[u]-B[e];
			pop(X[e]);
		}
		else
		{
			int v=query(Y[e]), u=X[e];
			B[e]=A[v];
			A[u]=A[v];
			push(X[e]);
		}
		P[e]^=1;
	}
	while(Q--)
	{
		int t;
		scanf("%d", &t);
		printf("%d\n", A[query(t)]);
	}
}

 

#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N, M, Q;
pii E[MAXN+10];
vector<int> A[MAXN+10];

vector<pii> adj[MAXN+10];
int sz[MAXN+10], del[MAXN+10];
int par[MAXN+10], edge[MAXN+10], head[MAXN+10];

void getsz(int now, int bef)
{
	sz[now]=1;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		par[nxt.first]=now;
		edge[nxt.first]=nxt.second;
		getsz(nxt.first, now);
		sz[now]+=sz[nxt.first];
	}
}

int getcen(int now, int bef, int S)
{
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[nxt.first]>S/2) return getcen(nxt.first, now, S);
	}
	return now;
}

int idx[MAXN+10], invidx[MAXN+10], cnt;

struct UF
{
	int par[MAXN+10];
	int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
	int Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		if(x==y) return x;
		par[x]=y;
		return y;
	}
}uf;

set<int> S[MAXN+10];
vector<int> V;

void hld(int now, int bef)
{
	//printf("!%d\n", now);
	V.push_back(now);
	idx[now]=++cnt;
	invidx[idx[now]]=now;
	int heavy=0;
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(sz[heavy]<sz[nxt.first]) heavy=nxt.first;
	}

	if(heavy==0) return;
	head[heavy]=head[now];
	hld(heavy, now);

	for(auto nxt : adj[now])
	{	
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		if(nxt.first==heavy) continue;
		head[nxt.first]=nxt.first;
		hld(nxt.first, now);
	}
}

int col[MAXN+10], val[MAXN+10], ts[MAXN+10], te[MAXN+10];
int ans[MAXN+10];

void fs(int now)
{
	for(auto it : V)
	{
		uf.par[it]=it;
		col[it]=1;
		val[it]=it;
		S[it].clear();
		ts[it]=M+1;
	}

	for(auto it : V) S[head[it]].insert(idx[it]);

	vector<pii> VT;
	for(auto it : V) if(it!=now) for(auto jt : A[edge[it]]) VT.push_back({jt, it});
	sort(VT.begin(), VT.end());
	
	for(auto it : VT)
	{
		int v=it.second, t=it.first;
		if(col[v])
		{
			S[head[v]].erase(idx[v]);

			if(val[v])
			{
				int u=v;
				while(1)
				{
					auto pt=S[head[u]].upper_bound(idx[u]);
					if(pt==S[head[u]].begin()) u=par[head[u]];
					else { u=invidx[*(--pt)]; break; }
				}

				if(u==now)
				{
					if(val[v]) ts[val[v]]=t;
				}
				else
				{
					if(val[u]==0) val[u]=val[v];
					else val[u]=uf.Union(val[u], val[v]);
				}
				val[v]=0;
			}
			col[v]=0;
		}
		else	
		{
			S[head[v]].insert(idx[v]);
			col[v]=1;
		}
	}

	for(auto it : V) if(it!=now) ts[it]=ts[uf.Find(it)];
}

void fe(int now)
{
	for(auto it : V)
	{
		uf.par[it]=it;
		col[it]=1;
		val[it]=it;
		S[it].clear();
		te[it]=0;
	}

	for(auto it : V) S[head[it]].insert(idx[it]);

	vector<pii> VT;
	for(auto it : V) if(it!=now) for(auto jt : A[edge[it]]) VT.push_back({jt, it});
	sort(VT.begin(), VT.end(), greater<pii>());
	
	for(auto it : VT)
	{
		int v=it.second, t=it.first;
		if(col[v])
		{
			S[head[v]].erase(idx[v]);

			if(val[v])
			{
				int u=v;
				while(1)
				{
					auto pt=S[head[u]].upper_bound(idx[u]);
					if(pt==S[head[u]].begin()) u=par[head[u]];
					else { u=invidx[*(--pt)]; break; }
				}

				if(u==now)
				{
					if(val[v]) te[val[v]]=t;
				}
				else
				{
					if(val[u]==0) val[u]=val[v];
					else val[u]=uf.Union(val[u], val[v]);
				}
				val[v]=0;
			}
			col[v]=0;
		}
		else	
		{
			S[head[v]].insert(idx[v]);
			col[v]=1;
		}

		for(auto it : V) if(it!=now) te[it]=te[uf.Find(it)];
	}

	for(auto it : V) if(it!=now) te[it]=te[uf.Find(it)];
}

void dfs2(int now, int bef, vector<int> &VV)
{
	VV.push_back(now);
	for(auto nxt : adj[now])
	{
		if(nxt.first==bef) continue;
		if(del[nxt.first]) continue;
		dfs2(nxt.first, now, VV);
	}
}

void decomp(int now)
{
	int i, j;
	getsz(now, now);
	now=getcen(now, now, sz[now]);
	getsz(now, now);

	V.clear();
	head[now]=now;
	hld(now, now);

	fs(now); fe(now);
	//for(auto it : V) printf("%d : %d %d\n", it, ts[it], te[it]);

	for(auto it : V) if(it!=now && ts[it]<=M) ans[now]++;
	for(auto it : V) if(it!=now && te[it]>0) ans[it]++;

	vector<int> VV;
	for(auto it : V) if(it!=now) VV.push_back(ts[it]);
	sort(VV.begin(), VV.end());
	for(auto it : V) if(it!=now) ans[it]+=lower_bound(VV.begin(), VV.end(), te[it])-VV.begin();

	for(auto nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		vector<int> chd, VVV;
		dfs2(nxt.first, now, chd);
		for(auto it : chd) VVV.push_back(ts[it]);
		sort(VVV.begin(), VVV.end());
		for(auto it : chd) ans[it]-=lower_bound(VVV.begin(), VVV.end(), te[it])-VVV.begin();
	}

	//for(auto it : V) printf("ANS %d : %d\n", it, ans[it]);
	
	del[now]=true;
	for(auto nxt : adj[now])
	{
		if(del[nxt.first]) continue;
		decomp(nxt.first);
	}
}

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &Q);
	for(i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E[i]={u, v};
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
	}
	for(i=1; i<=M; i++)
	{
		int t;
		scanf("%d", &t);
		A[t].push_back(i);
	}
	for(i=1; i<N; i++) if(A[i].size()%2) A[i].push_back(M+1);
	decomp(1);
	
	for(i=1; i<=N; i++) ans[i]++;
	while(Q--)
	{
		int t;
		scanf("%d", &t);
		printf("%d\n", ans[t]);
	}
}