hud 4718 The LCIS on the Tree(树链剖分+线段树区间合并)(一)

思路：hdu 3308的加强版。先进行树链剖分，树链剖分后建线段树，树链剖分后一条链上的点在线段树中编号是连续的，所以只能在线段树上查询一条链上的区间信息，所给的点肯定不全是在一条链上的，所以我们求出的是一些区间，而这些区间还要合并起来求最大LCIS，在树上操作的时候是从度数大的点向上求的，有一条路径求的是下降的序列，所以线段树要统计两种序列的信息。每一次线段树的查找返回的结果应该是从该点到所在链的顶点或者一条链上两点的路径信息。求出来的序列合并应该注意顺序。

#include    
#include     
#include     
using namespace std;    
const int N=100100;  
int a[N],head[N],num,son[N],sz[N],father[N],ti[N],idx,dep[N],top[N],cot[N],cnt;  
struct edge  
{  
    int st,ed,next;  
}e[N*10];  
void addedge(int x,int y)  
{  
    e[num].ed=y;e[num].next=head[x];head[x]=num++;  
}  
int max(int a,int b)  
{  
    if(a>b)return a;  
    return b;  
}  
//**********************树链剖分************************  
void find_son(int u)  
{  
    int i,v;  
    son[u]=0;sz[u]=1;  
    for(i=head[u];i!=-1;i=e[i].next)  
    {  
        v=e[i].ed;        
        if(v==father[u])continue;  
        dep[v]=dep[u]+1;  
        father[v]=u;  
        find_son(v);  
        sz[u]+=sz[v];  
        if(sz[v]>sz[son[u]])son[u]=v;  
    }  
}  
void find_time(int u,int fa)    
{    
    int i,v;  
    ti[u]=idx++;//该点在线段树中的编号  
    top[u]=fa;//该点所在链的顶点  
    cot[ti[u]]=a[u];  
    if(son[u]!=0)find_time(son[u],top[u]);    
    for(i=head[u];i!=-1;i=e[i].next)    
    {  
        v=e[i].ed;  
        if(v==father[u]||v==son[u])continue;    
        find_time(e[i].ed,e[i].ed);//该链的顶点就是该点  
    }  
}  
//*****************线段树*************************  
struct Tree  
{  
    int R,L,Rn,Ln,len;  
    int ml,Rl,Ll;//最长LCIS，左边最长LCIS，右边最长LCIS  
    int dml,dRl,dLl;//下降序列长度  
}T[N*10];  
void buildTree(int L,int R,int id)  
{  
    T[id].L=L;T[id].R=R;T[id].len=R-L+1;  
    if(L==R)  
    {  
        T[id].Ln=T[id].Rn=cot[L];  
        T[id].ml=T[id].Ll=T[id].Rl=1;  
        T[id].dml=T[id].dLl=T[id].dRl=1;  
        return ;  
    }  
    int mid=(L+R)>>1,li=id<<1,ri=li+1;  
    buildTree(L,mid,li);  
    buildTree(mid+1,R,ri);  
  
    T[id].Ln=T[li].Ln;T[id].Rn=T[ri].Rn;      
    T[id].Ll=T[li].Ll;T[id].Rl=T[ri].Rl;  
    T[id].dLl=T[li].dLl;T[id].dRl=T[ri].dRl;      
    T[id].ml=max(T[li].ml,T[ri].ml);  
    T[id].dml=max(T[li].dml,T[ri].dml);   
    if(T[li].RnT[ri].Ln)  
    {  
        T[id].dml=max(T[id].dml,T[li].dRl+T[ri].dLl);  
        if(T[li].dRl==T[li].len)  
            T[id].dLl=T[li].dLl+T[ri].dLl;  
        if(T[ri].dRl==T[ri].len)  
            T[id].dRl=T[li].dRl+T[ri].dRl;    
    }  
}  
void addTree(int li,int ri,int id)//将两个区间li,ri合并成id  
{  
    T[id].len=T[li].len+T[ri].len;  
    T[id].Ln=T[li].Ln;T[id].Rn=T[ri].Rn;      
    T[id].Ll=T[li].Ll;T[id].Rl=T[ri].Rl;  
    T[id].dLl=T[li].dLl;T[id].dRl=T[ri].dRl;  
    T[id].ml=max(T[li].ml,T[ri].ml);  
    T[id].dml=max(T[li].dml,T[ri].dml);  
      
    if(T[li].Rn





T[ri].Ln)  
    {  
        T[id].dml=max(T[id].dml,T[li].dRl+T[ri].dLl);  
        if(T[li].dRl==T[li].len)  
            T[id].dLl=T[li].dLl+T[ri].dLl;  
        if(T[ri].dRl==T[ri].len)  
            T[id].dRl=T[li].dRl+T[ri].dRl;    
    }  
}  
int anson(int l, int r)  
{  
    int ans = max(T[l].dml, T[r].ml);  
    if(T[l].Ln < T[r].Ln)  
        return max(ans,T[l].dLl+T[r].Ll);  
    return ans;  
}  
int query(int L,int R,int id)  
{  
    if(T[id].L==L&&T[id].R==R)  
        return id;  
    int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li+1;  
    if(mid>=R)  
        return query(L,R,li);  
    else if(middep[top[y]])  
        {  
            op=query(ti[top[x]],ti[x],1);  
            x=father[top[x]];  
            if(xp==-1)xp=op;  
            else   
            {  
                addTree(op,xp,++cnt);//合并的时候注意，新求出来的序列应该加在原序列的左边  
                xp=cnt;  
            }  
        }  
        else   
        {  
            op=query(ti[top[y]],ti[y],1);  
            y=father[top[y]];  
            if(yp==-1)yp=op;  
            else  
            {  
                addTree(op,yp,++cnt);  
                yp=cnt;  
            }  
        }  
    }    
    if(dep[x]>=dep[y])  
    {  
        op=query(ti[y],ti[x],1);  
        if(xp==-1)xp=op;  
        else   
        {  
            addTree(op,xp,++cnt);  
            xp=cnt;  
        }  
    }  
    else   
    {  
        op=query(ti[x],ti[y],1);  
        if(yp==-1)yp=op;  
        else  
        {  
            addTree(op,yp,++cnt);  
            yp=cnt;  
        }  
    }   
    if(xp==-1)  return T[yp].ml;//求出来的y的路径是正向的  
    if(yp==-1)  return T[xp].dml;//x的路径是逆向的  
    return anson(xp,yp);  
}  
int main()  
{  
    int i,n,m,t,x,y,op=1;  
    scanf("%d",&t);  
    while(t--)  
    {  
        memset(head,-1,sizeof(he