Centroid Decomposition

https://www.quora.com/q/threadsiiithyderabad/Centroid-Decomposition-of-a-Tree

 

Centroid Decomposition 은 트리에서 분할정복을 할 수 있도록 해주는 방법이다.

 

분할정복은 다음과 같이 생각해볼 수 있다.

어떤 구간 [l, r]을 잡아도 어떠한 가운데 점 k를 잡아서 [l, k], [k+1, r] 로 쪼갤 수 있다.

또한, 분할정복에서 나오는 k들에서 [a, k] 와 같은 구간의 개수는 $O(NlogN)$ 개이다.

 

단순히 말해, 모든 구간들을 $O(NlogN)$ 개의 구간 2개의 합으로 나타낼 수 있으니 이 $NlogN$ 개를 관리하여 해결한다는 것이다.

 

트리에서도 Centroid 라는 점은 그 점을 제거하면 나오는 서브트리의 집합이 $N/2$ 이하의 노드를 갖는 점이다.

루트를 잡고 크기가 $N/2$ 보다 큰 서브트리 쪽으로 이동하는 것을 계속 반복해주면 centroid 를 찾을 수 있다.

 

이제 현재 트리에서의 centroid 를 찾고 그 점을 삭제한다.

그 후 남은 트리들로 쪼개주고 이 과정을 계속 반복하면 된다.

 

이를 이용하면 다양한 업데이트나 쿼리에서 Centroid Tree의 높이가 최대 $logN$ 이기 때문에 효율적으로 처리해줄 수 있다.

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

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

const int MAXN = 1e5;
const int INF = 987654321;

int N, Q;
vector<int> adj[MAXN+10];
int par[MAXN+10][30], dep[MAXN+10];

int sz[MAXN+10], cenpar[MAXN+10], ans[MAXN+10];
bool del[MAXN+10];

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

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

void decomp(int now, int bef)
{
    getsz(now, now);
    now=getcen(now, now, sz[now]);
    del[now]=true;
    cenpar[now]=bef;

    for(int nxt : adj[now])
    {
        if(del[nxt]) continue;
        decomp(nxt, now);
    }
}

void dfs(int now, int bef, int depth)
{
    par[now][0]=bef;
    dep[now]=depth;
    for(int nxt : adj[now])
    {
        if(nxt==bef) continue;
        dfs(nxt, now, depth+1);
    }
}

int lca(int u, int v)
{
    int i, j;
    if(dep[u]>dep[v]) swap(u, v);
    for(i=20; i>=0; i--) if(dep[par[v][i]]>=dep[u]) v=par[v][i];
    if(v==u) return v;
    for(i=20; i>=0; i--) if(par[v][i]!=par[u][i]) v=par[v][i], u=par[u][i];
    return par[u][0];
}

int dist(int u, int v)
{
    int w=lca(u, v);
    return dep[u]+dep[v]-dep[w]*2;
}

void update(int u)
{
    int v=u;
    while(v)
    {
        ans[v]=min(ans[v], dist(u, v));
        v=cenpar[v];
    }
}

int query(int u)
{
    int v=u;
    int ret=INF;
    while(v)
    {
        ret=min(ret, dist(u, v)+ans[v]);
        v=cenpar[v];
    }
    return ret;
}

int main()
{
    int i, j;

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

    decomp(1, 0);
    dfs(1, 0, 1);
    for(i=1; i<=20; i++) for(j=1; j<=N; j++) par[j][i]=par[par[j][i-1]][i-1];
    for(i=1; i<=N; i++) ans[i]=INF;

    update(1);
    while(Q--)
    {
        int t, u;
        scanf("%d%d", &t, &u);
        if(t==1) update(u);
        else printf("%d\n", query(u));
    }
}