bzoj2588 Spoj 10628. Count on a tree

bzoj2588 Spoj 10628. Count on a tree

题意：

n点树，m个询问求点u到点v路径上第k小的点权。强制在线。n，m≤100000

题解：

用主席树维护某节点到根节点的权值数量sz，建树过程可以由父亲节点递推。询问就用倍增求出lca，然后路径上的sz值就为sz[u]-sz[lca]+sz[v]-sz[fa[lca]]。反思：本弱倍增数组写反了，疯狂reQAQ~

代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define maxn 100500
using namespace std;

int f[18][maxn],rt[maxn],dep[maxn],ch[maxn*35][2],sz[maxn*35],v[maxn],id[maxn],n,m,size,last,tot;
struct e{int t,n;}; e es[maxn*2]; int ess,g[maxn];
void pe(int f,int t){es[++ess]=(e){t,g[f]}; g[f]=ess; es[++ess]=(e){f,g[t]}; g[t]=ess;}
struct abc{int v,id;}; abc abcd[maxn]; bool cmp(abc a,abc b){return a.v<b.v;}
inline int read(){
    char ch=getchar(); int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f*x;
}
void build1(int &x,int l,int r){
    x=++size; sz[x]=ch[x][0]=ch[x][1]=0; if(l==r)return;
    int mid=(l+r)>>1; build1(ch[x][0],l,mid); build1(ch[x][1],mid+1,r);
}
void insert(int &x,int l,int r,int val){
    size++; sz[size]=sz[x]+1; ch[size][0]=ch[x][0]; ch[size][1]=ch[x][1]; x=size; if(l==r)return;
    int mid=(l+r)>>1; if(val<=mid)insert(ch[x][0],l,mid,val); if(val>mid)insert(ch[x][1],mid+1,r,val);
}
void dfs(int x,int fa){
    rt[x]=rt[fa]; insert(rt[x],1,tot,v[x]);
    for(int i=g[x];i;i=es[i].n)if(es[i].t!=fa){
        f[0][es[i].t]=x; dep[es[i].t]=dep[x]+1; dfs(es[i].t,x);
    }
}
void build2(){
    for(int i=1;(1<<i)<=n;i++)inc(j,1,n)f[i][j]=f[i-1][f[i-1][j]];
}
int LCA(int u,int v){
    if(dep[u]<dep[v])swap(u,v); int t=dep[u]-dep[v];
    for(int i=0;(1<<i)<=n;i++)if(t&(1<<i))u=f[i][u];
    for(int i=16;i>=0;i--)if(f[i][u]!=f[i][v])u=f[i][u],v=f[i][v];
    return u==v?u:f[0][u];
}
int solve(int u,int v,int k){
    int lca=LCA(u,v),l=1,r=tot,x1=rt[v],x2=rt[f[0][lca]],x3=rt[u],x4=rt[lca];
    while(l<r){
        int mid=(l+r)>>1,tmp=sz[ch[x1][0]]-sz[ch[x2][0]]+sz[ch[x3][0]]-sz[ch[x4][0]];
        if(tmp>=k)
            r=mid,x1=ch[x1][0],x2=ch[x2][0],x3=ch[x3][0],x4=ch[x4][0];
        else
            k-=tmp,l=mid+1,x1=ch[x1][1],x2=ch[x2][1],x3=ch[x3][1],x4=ch[x4][1];
    }
    return l;
}
int main(){
    n=read(); m=read(); inc(i,1,n)abcd[i]=(abc){read(),i}; inc(i,1,n-1){int a=read(),b=read(); pe(a,b);}
    sort(abcd+1,abcd+1+n,cmp);
    inc(i,1,n){if(i==1||abcd[i].v!=abcd[i-1].v)++tot,id[tot]=abcd[i].v; v[abcd[i].id]=tot;}
    size=0; build1(rt[0],1,tot); dfs(1,0); build2();
    inc(i,1,m){
        int u=read()^last,v=read(),k=read(); last=id[solve(u,v,k)]; printf("%d",last); if(i!=m)puts("");
    }
    return 0;
}

20160621