TOJ 84 樹鏈剖分4

allenwhale

這題樹鏈剖分最基本的練習題

先簡單說一下樹練剖分的基本概念
簡單來說就是把二維的樹壓到一維的線段樹上，聽起來頗神奇的
但是怎麼壓卻是一個重點
為了達到期望的複雜度，所以有重鏈與輕鏈之分
重鏈就是該結點的子結點中擁有最多兒子、孫子的那條路

詳細參考資料:
http://www.baike.com/wiki/%E6%A0%91%E9%93%BE%E5%89%96%E5%88%86
http://quartergeek.com/summary-of-heavy-light-decomposition/

除了樹鏈剖分外，還要熟練線段樹的基本操作

code說長不長說短不短，140行左右而已
但是樹鏈剖分不但是稍微高級的演算法，還是熟練基礎演算法的好題目

AC code:

[C++] 純文本查看 復制代碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#define MS(s,v) memset(s,v,sizeof(s))
#define foreach(it,x) for(__typeof(x.begin()) it=x.begin(),eit=x.end();it!=eit;it++)
#define SIZE(x) ((int)x.size())
#define INF 0x3f3f3f3f
#ifdef __ALLEN
 #define __lld "%I64d"
#else
 #define __lld "%lld"
#endif
#define MAXN 200010
using namespace std;
int N,fa[MAXN],tid[MAXN],id[MAXN],dep[MAXN],top[MAXN],sz[MAXN],son[MAXN],t;
vector<int>vc[MAXN];
int dfs_1(int root,int f)
{
    dep[root]=dep[f]+1;sz[root]=1;fa[root]=f;son[root]=0;
    foreach(it,vc[root])
    {
        if(*(it)==f)continue;
        sz[root]+=dfs_1(*(it),root);
        if(sz[son[root]]<sz[*(it)])son[root]=*(it);
    }
    return sz[root];
}
void dfs_2(int root,int f)
{
    top[root]=f;id[t]=root;tid[root]=t++;
    if(son[root])dfs_2(son[root],f);
    foreach(it,vc[root])
    {
        if(*(it)==fa[root]||*(it)==son[root])continue;
        dfs_2(*(it),*(it));
    }
}
struct Segtree
{
    int L,R,c,pos;
    inline int mid()
    {
        return (L+R)>>1;
    }
}St[MAXN<<2];
void buildtree(int l,int r,int idx)
{
    St[idx].L=l,St[idx].R=r,St[idx].c=St[idx].pos=0;
    if(l==r)return;
    int mid=St[idx].mid();
    buildtree(l,mid,idx<<1);
    buildtree(mid+1,r,(idx<<1)|1);
}
void modify(int x,int idx)
{
    if(St[idx].L==St[idx].R)
    {
        St[idx].c^=1;
        if(St[idx].c)St[idx].pos=id[St[idx].L];
        else St[idx].pos=0;
        return ;
    }
    int mid=St[idx].mid();
    if(x<=mid)modify(x,idx<<1);
    else modify(x,(idx<<1)|1);
    if(St[idx<<1].c)
    {
        St[idx].c=St[idx<<1].c;
        St[idx].pos=St[idx<<1].pos;
    }
    else
    {
        St[idx].c=St[(idx<<1)|1].c;
        St[idx].pos=St[(idx<<1)|1].pos;
    }
}
int ask(int l,int r,int idx)
{
    if(St[idx].L==l&&St[idx].R==r)
    {
        return St[idx].pos;
    }
    int mid=St[idx].mid();
    if(r<=mid)return ask(l,r,idx<<1);
    else if(l>=mid+1)return ask(l,r,(idx<<1)|1);
    else 
    {
        int tmp=ask(l,mid,idx<<1);
        if(tmp)return tmp;
        return ask(mid+1,r,(idx<<1)|1);
    }
}
int query(int x)
{
    int y=1;
    int ans=-1;
    while(top[x]!=top[y])
    {
        //printf("  %d\n",x);
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        int tmp=ask(tid[top[x]],tid[x],1);
        if(tmp)ans=tmp;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    int tmp=ask(tid[x],tid[y],1);
    if(tmp)ans=tmp;
    return ans;
}
void init()
{
    for(int i=0;i<=N;i++)vc[i].clear();
    dep[1]=0;son[0]=0;sz[0]=0;t=1;
}
int main()
{
    int Q;
    scanf("%d %d",&N,&Q);
    init();
    for(int i=0;i<N-1;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        vc[a].push_back(b);
        vc[b].push_back(a);
    }
    dfs_1(1,1);
    dfs_2(1,1);
    buildtree(1,N,1);
    while(Q--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        if(a==0)modify(tid[b],1);
        else printf("%d\n",query(b));
    }
    return 0;
}