hud 4718 The LCIS on the Tree(树链剖分+线段树区间合并)
题意：给出一棵树，有Q个询问，x到y之间的路径所有边组成的序列，求该序列的LCIS。
思路：hdu 3308的加强版。先进行树链剖分，树链剖分后建线段树，树链剖分后一条链上的点在线段树中编号是连续的，所以只能在线段树上查询一条链上的区间信息，所给的点肯定不全是在一条链上的，所以我们求出的是一些区间，而这些区间还要合并起来求最大LCIS，在树上操作的时候是从度数大的点向上求的，有一条路径求的是下降的序列，所以线段树要统计两种序列的信息。每一次线段树的查找返回的结果应该是从该点到所在链的顶点或者一条链上两点的路径信息。求出来的序列合并应该注意顺序。
#include<stdio.h> #include <iostream> #include <string.h> 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，右边最长LCISint 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].Rn<T[ri].Ln)//左区间和右区间可以合并{T[id].ml=max(T[id].ml,T[li].Rl+T[ri].Ll);if(T[li].Rl==T[li].len)//左区间整个区间是LCIS，更新该区间的左边LCIS长度。T[id].Ll=T[li].Ll+T[ri].Ll;if(T[ri].Rl==T[ri].len)T[id].Rl=T[li].Rl+T[ri].Rl;}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;}}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].ml=max(T[id].ml,T[li].Rl+T[ri].Ll);if(T[li].Rl==T[li].len)T[id].Ll=T[li].Ll+T[ri].Ll;if(T[ri].Rl==T[ri].len)T[id].Rl=T[li].Rl+T[ri].Rl;}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(mid<L) return query(L,R,ri);else {int ls=query(L,mid,li);int rs=query(mid+1,R,ri);addTree(ls,rs,++cnt);return cnt;}}int lca(int x,int y) { if(x==y)return 1; cnt=4*N;int xp=-1,yp=-1,op;//xp表示从x点所走的路径合并的区间，yp代表y while(top[x]!=top[y])//两点不在同一条链上 { if(dep[top[x]]>dep[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(head));num=0;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=2;i<=n;i++){scanf("%d",&x);addedge(x,i);}father[1]=sz[0]=0;dep[1]=idx=1;find_son(1);find_time(1,1);buildTree(1,n,1);scanf("%d",&m);printf("Case #%d:\n",op++);while(m--){scanf("%d%d",&x,&y);printf("%d\n",lca(x,y));}if(t) printf("\n");}return 0;}