【填坑向】spoj COT/bzoj2588 Count on a tree

这题是学主席树的时候就想写的，，，

但是当时没写（懒）

现在来填坑

= =日常调半天lca（考虑以后背板）

主席树还是蛮好写的，但是代码出现重复，不太好，导致调试的时候心里没底（虽然事实证明主席树部分没出问题）

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 struct lis{    int x,id;} li[];

 struct nod{    int num,ls,rs;} t[];

 int n,m,x,y,z,sum=,N=,lastans=;

 int to[],nex[],list[];

 int a[],h[],fir[],root[],f[],pos[];

 int log[],near[],rmq[][];

 bool operator<(lis a,lis b){    return a.x<b.x;}

 void add(int x,int y,int z){    to[z]=y;nex[z]=fir[x];fir[x]=z;}

 inline int lca(int x,int y){    if(x>y)    swap(x,y);

     return (h[rmq[log[y-x+]][x]]<h[rmq[log[y-x+]][y-near[y-x+]+]])?

     rmq[log[y-x+]][x]:rmq[log[y-x+]][y-near[y-x+]+];}

 void build(int now,int fa)

 {

     f[now]=fa;root[now]=++sum;

     int com=root[fa],cha=root[now],l=,r=n;

     while(l<r)

         if(a[now]>(l+r)/)

             l=(l+r)/+,t[cha]=(nod){t[com].num+,t[com].ls,++sum},cha=sum,com=t[com].rs;

         else

             r=(l+r)/,t[cha]=(nod){t[com].num+,++sum,t[com].rs},cha=sum,com=t[com].ls;

     list[++N]=now;pos[now]=N;t[cha]=(nod){t[com].num+,,};h[now]=h[fa]+;

     for(int i=fir[now];i;i=nex[i])

     if(to[i]!=fa)

         build(to[i],now),list[++N]=now;

 }

 void que(int x,int y,int z)

 {

     int l=,r=n,lc=lca(pos[x],pos[y]),lcc=f[lc];

     x=root[x],y=root[y],lc=root[lc],lcc=root[lcc];

     while(l<r)

         if(t[t[x].ls].num+t[t[y].ls].num-t[t[lc].ls].num-t[t[lcc].ls].num<z)

             l=(l+r)/+,z-=t[t[x].ls].num+t[t[y].ls].num-t[t[lc].ls].num-t[t[lcc].ls].num,

             x=t[x].rs,y=t[y].rs,lc=t[lc].rs,lcc=t[lcc].rs;

         else

             r=(l+r)/,x=t[x].ls,y=t[y].ls,lc=t[lc].ls,lcc=t[lcc].ls;

     lastans=li[l].x;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++)

         scanf("%d",&li[i].x),li[i].id=i;

     sort(li+,li+n+);

     for(int i=;i<=n;i++)

         a[li[i].id]=i;

     for(int i=;i<n;i++)

         scanf("%d%d",&x,&y),add(x,y,i),add(y,x,i+n);

     build(,);

     for(int i=;i<=N;i++)

         rmq[][i]=list[i];

     for(int i=,j=,k=;i<=N;log[i]=j,near[i]=k,i++)

         if(i>k*)    j++,k*=;

     for(int i=,k=;k<=N;i++,k*=)

         for(int j=;j<=N-k+;j++)

             rmq[i][j]=(h[rmq[i-][j]]<h[rmq[i-][j+k/]])?rmq[i-][j]:rmq[i-][j+k/];

     for(int i=;i<=m;i++)

         scanf("%d%d%d",&x,&y,&z),que(/*lastans^*/x,y,z),printf(i<m?"%d\n":"%d",lastans);

     return ;

 } //lastans^加上以后就是强在，bzoj上的题；不加就是不强在，spoj上的题

顺便吐槽：spoj上内存限制1.5G实在太6，，，

导致我乱开数组，交bzoj的时候MLE了很多发