树链剖分，是个很神奇蛇皮的算法，他巧妙的运用了与分块类似的思想，来加速整块代码。不过，对于某些毒瘤题来说，树链剖分很可能会爆栈，如：一本通:染色。不过洛谷还好，不会爆栈。。。

那么这个时候，我们就需要手动模拟来实现非递归版本的树链剖分了。

注意到，整块树链剖分的代码中使用了递归的地方:

1.两次dfs求dfs序

2.线段树

而其中线段树，我们完全不用改。因为，它的运行层数才log(n)层（要改的话可以去学下zkw线段树）

那么，我们着重看两次dfs。

第一次dfs:

这次dfs，需要我们求出所有节点的:

1.父亲

2.层数

3.子树大小(包括自身)

4.重儿子

首先是层数和父亲，这个咱们普通地扫一遍bfs就ok了，不用多说。

然后，我们可以用vector倒扫法或者topo序法两种方法倒扫一遍整个树，就像做树型dp样，再搞一遍bfs，就可以求出3和4了，这里不做过多阐述，直接放一波代码(我是用的几乎没人用的vector倒扫法(其实是我某场考试yy出来的产物)): 

queue<int>s;
s.push(x);
dep[x]=1;
ceng[1].push_back(x);//每层save 
while(!s.empty()){//第一遍bfs 
    int x=s.front();
    s.pop();
    for(int i=las[x];i;i=t[i].nex){
        int v=t[i].v;
        if(!dep[v]){
            dep[v]=dep[x]+1,fa[v]=x;
            ceng[dep[v]].push_back(v);//每层save 
            maxe=dep[v];//记录最大层数 
            s.push(v);
        }
    }
}
int now=maxe;//倒扫 
while(now){
    int len=ceng[now].size();
    for(int i=0;i<len;++i){
        int u=ceng[now][i];//当前节点 
        siz[u]=1;
        int maxt=0;
        for(int j=las[u];j;j=t[j].nex){
            int v=t[j].v;
            if(dep[v]>dep[u]){
                siz[u]+=siz[v];//求子树大小 
                if(siz[v]>maxt){//求重儿子 
                    son[u]=v;
                    maxt=siz[v];
                }
            }
        }
    }
    now--;
}

第二次dfs:

本次dfs是要求每个节点的:

1.链顶

2.dfs序

3.相应dfs序所对应的颜色

那么，求这个，就需要我们用"栈"这个神奇的sb的玩意儿来模拟dfs

我们利用栈先进后出的性质，优先拿出一个点的重儿子，然后再利用重儿子更新重孙子(滑稽)。。。

这样我们就可以按dfs的思路更新完一条树链了。

然后依次类推。。。

那么怎么优先更新重儿子呢？栈啊，他是先进后出，于是，我们就让它最后加入就好了啊。。。

代码(我这里用的stl,相信大家都看得懂,还有,我用的pair,来模拟dfs传入的两个值): 

stack<pair<int,int> >s;//定义pair栈 
s.push(make_pair(1,1));
while(!s.empty()){
    int x=s.top().first,y=s.top().second;//取出栈顶 
    s.pop();//弹出栈顶 
    top[x]=y,id[x]=++cnt,col[cnt]=W[x];//各种赋值 
    for(int i=las[x];i;i=t[i].nex){
        int v=t[i].v;
        if(v!=fa[x]&&v!=son[x]){
            s.push(make_pair(v,v));
        }
    }
    if(son[x]){
        s.push(make_pair(son[x],y));//最后加入重儿子节点 
    }
}

到此，我们就成功实现了非递归的树链剖分了，撒花✿✿ヽ(°▽°)ノ✿✿