非递归的树链剖分

int son[maxn],num[maxn],fa[maxn],top[maxn],p[maxn],fp[maxn],pos,depth[maxn]；
vector<int>F[maxn];
int D[maxn],TOPD[maxn];
int NU[maxn];
int IN[maxn];
void dfs(){
    memset(NU,0,sizeof(NU));
    memset(IN,0,sizeof(IN));
    int cnt=0;
    IN[1]=0;
    D[cnt++]=1;
    depth[1]=0;fa[1]=0;
    son[1]=-1;
    num[1]=1;
    while(cnt>=1){
         int cur=D[cnt-1];
        for(int &i=NU[cur]; i<F[cur].size(); i++ ){
            int to=F[cur][i];
            if(to==fa[cur]) {
              continue;
            }
            if(IN[to]){
             num[cur]+=num[to];
             if( son[ cur ] == -1 || num[ son[cur] ]< num[to] ) son[cur]=to;
             continue;
            }
            fa[to]=cur;
            IN[to]=1;
            depth[to]=depth[ cur  ]+1;
            son[to]=-1;
            num[to]=1;
            D[cnt++]=to;
            break;
        }
        if(NU[cur]==F[cur].size())cnt--;
    }
}
int BU[maxn];
void finde(){
    memset(NU,0,sizeof(NU));
    memset(BU,0,sizeof(BU));
    memset(IN,0,sizeof(IN));
    int cnt=0;
    IN[1]=0;
    D[cnt]=1;TOPD[cnt++]=1;
    top[1]=1;pos++;p[1]=pos;fp[pos]=1;
    while(cnt>=1){
         int cur=D[cnt-1];
         if(BU[cur]||son[cur]==-1)
          {
            for(int &i=NU[cur]; i<F[cur].size(); i++ ){
             int to=F[cur][i];
             if(to==fa[cur]||to==son[cur]||IN[to])continue;
             IN[to]=1;
             top[to]=to;
             pos++;
             p[to]=pos;
             fp[pos]=to;
             D[cnt]=to; TOPD[cnt++]=to; break;
           }
        }else{
          BU[cur]=1;
          int to = son[cur];
          top[to]=TOPD[cnt-1];
          pos++;
          p[to]=pos;
          fp[pos]=to;
          D[cnt]=to;TOPD[cnt]=TOPD[cnt-1];cnt++;
        }
        if(NU[cur]==F[cur].size())cnt--;
    }



}

 邻接表形式

int son[maxn],num[maxn],fa[maxn],top[maxn],p[maxn],fp[maxn],pos,depth[maxn],val[maxn];
int H[maxn],nx[maxn*2],to[maxn*2],numofE;
int D[maxn],TOPD[maxn];
int NU[maxn];
int IN[maxn];
void dfs(int n){
    for(int i=0;i<=n; i++)
        NU[i]=H[i];
    memset(IN,0,sizeof(IN));
    int cnt=0;
    IN[1]=0;
    D[cnt++]=1;
    depth[1]=0;fa[1]=0;
    son[1]=-1;
    num[1]=1;
    while(cnt>=1){
         int cur=D[cnt-1];
        for(int &i=NU[cur]; i; i=nx[i] ){
            int tto=to[i];
            if(tto==fa[cur]) {
              continue;
            }
            if(IN[tto]){
             num[cur]+=num[tto];
             if( son[ cur ] == -1 || num[ son[cur] ]< num[tto] ) son[cur]=tto;
             continue;
            }
            fa[tto]=cur;
            IN[tto]=1;
            depth[tto]=depth[ cur  ]+1;
            son[tto]=-1;
            num[tto]=1;
            D[cnt++]=tto;
            break;
        }
        if(NU[cur]==0)cnt--;
    }
}
void finde(int n){
    for(int i=0;i<=n;i++)
        NU[i]=H[i];
    memset(BU,0,sizeof(BU));
    memset(IN,0,sizeof(IN));
    int cnt=0;
    IN[1]=0;
    D[cnt]=1;TOPD[cnt++]=1;
    top[1]=1;pos++;p[1]=pos;fp[pos]=1;
    while(cnt>=1){
         int cur=D[cnt-1];
         if(BU[cur]||son[cur]==-1)
          {
            for(int &i=NU[cur]; i; i=nx[i] ){
             int tto=to[i];
             if(tto==fa[cur]||tto==son[cur]||IN[tto])continue;
             IN[tto]=1;
             top[tto]=tto;
             pos++;
             p[tto]=pos;
             fp[pos]=tto;
             D[cnt]=tto; TOPD[cnt++]=tto; break;
           }
        }else{
          BU[cur]=1;
          int tto = son[cur];
          top[tto]=TOPD[cnt-1];
          pos++;
          p[tto]=pos;
          fp[pos]=tto;
          D[cnt]=tto;TOPD[cnt]=TOPD[cnt-1];cnt++;
        }
        if(NU[cur]==0)cnt--;
    }
}