BZOJ4539: [Hnoi2016]树

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,q,c=1;
int id[MAXN],pos[MAXN],tree_size[MAXN];
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
    return date*w;
}
namespace ST{
    int d=1,e=1;
    int head[MAXN],deep[MAXN],f[MAXN][20];
    struct Tree{
        int next,to;
    }a[MAXN<<1];
    inline void add(int x,int y){
        a[d].to=y;a[d].next=head[x];head[x]=d++;
        a[d].to=x;a[d].next=head[y];head[y]=d++;
    }
    void buildtree(int rt){
        tree_size[rt]=1;
        id[rt]=e;pos[e++]=rt;
        for(int i=head[rt];i;i=a[i].next){
            int will=a[i].to;
            if(!deep[will]){
                deep[will]=deep[rt]+1;
                f[will][0]=rt;
                buildtree(will);
                tree_size[rt]+=tree_size[will];
            }
        }
    }
    void step(){
        for(int i=1;i<=19;i++)
        for(int j=1;j<=n;j++)
        f[j][i]=f[f[j][i-1]][i-1];
    }
    int LCA(int x,int y){
        if(deep[x]<deep[y])swap(x,y);
        for(int i=19;i>=0;i--)if(deep[f[x][i]]>=deep[y])x=f[x][i];
        if(x==y)return x;
        for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
        return f[x][0];
    }
    inline long long dis(int x,int y){return abs(deep[x]-deep[y]);}
    inline long long dis_lca(int x,int y,int rt){return deep[LCA(x,y)]-deep[rt];}
}
namespace CT{
    int d=1,size=1,root[MAXN];
    struct Charman_Tree{
        int l,r,sum;
    }a[MAXN*22];
    struct Right{
        int root,x;
        long long v;
        friend bool operator <(const Right p,const Right q){return p.v<q.v;}
    }right[MAXN];
    void insert(int k,int l,int r,int &rt){
        a[size]=a[rt];rt=size++;
        a[rt].sum++;
        if(l==r)return;
        int mid=l+r>>1;
        if(k<=mid)insert(k,l,mid,a[rt].l);
        else insert(k,mid+1,r,a[rt].r);
    }
    int query(int i,int j,int l,int r,int k){
        if(l==r)return l;
        int mid=l+r>>1,t=a[a[j].l].sum-a[a[i].l].sum;
        if(k<=t)return query(a[i].l,a[j].l,l,mid,k);
        else return query(a[i].r,a[j].r,mid+1,r,k-t);
    }
    inline void buildtree(){
        root[0]=0;
        a[0].l=a[0].r=a[0].sum=0;
        for(int i=1;i<=n;i++){
            root[i]=root[i-1];
            insert(pos[i],0,n,root[i]);
        }
    }
    inline int kth(int l,int r,int k){return query(root[l],root[r],0,n,k);}
    inline void insert_node(int root,int x){
        right[d]=(Right){root,x,right[d-1].v+tree_size[root]};
        d++;
    }
    inline void query_node(long long v,int &root,int &y,int &x){
        Right p=*lower_bound(right+1,right+d,(Right){0,0,v});
        root=p.root;x=p.x;
        int rank=v+tree_size[root]-p.v;
        y=kth(id[root]-1,id[root]+tree_size[root]-1,rank);
    }
}
namespace BT{
    int d=1,head[MAXN],deep[MAXN],val[MAXN],f[MAXN][20];
    long long dis[MAXN];
    struct Tree{
        int next,to;
        long long w;
    }a[MAXN<<1];
    inline void add(int u,int v,long long w){
        a[d].to=v;a[d].w=w;a[d].next=head[u];head[u]=d++;
        a[d].to=u;a[d].w=w;a[d].next=head[v];head[v]=d++;
    }
    void buildtree(int rt){
        int will;
        for(int i=head[rt];i;i=a[i].next){
            will=a[i].to;
            if(!deep[will]){
                deep[will]=deep[rt]+1;
                dis[will]=dis[rt]+a[i].w;
                f[will][0]=rt;
                buildtree(will);
            }
        }
    }
    void step(){
        for(int i=1;i<=19;i++)
        for(int j=1;j<=c-1;j++)
        f[j][i]=f[f[j][i-1]][i-1];
    }
    int LCA(int x,int y,int &u,int &v){
        if(x==y)return x;
        if(deep[x]<deep[y]){swap(x,y);swap(u,v);}
        for(int i=19;i>=0;i--)if(deep[f[x][i]]>deep[y])x=f[x][i];
        if(f[x][0]==y){u=val[x];return y;}
        else if(deep[x]!=deep[y])x=f[x][0];
        for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
        u=val[x];v=val[y];
        return f[x][0];
    }
    inline long long dist(int u,int v,int lca){return dis[u]+dis[v]-dis[lca]*2;}
}
inline void solve(long long x,long long y){
	long long dist;
    int r1,x1,y1,h1;int r2,x2,y2,h2;
    CT::query_node(x,r1,y1,x1);CT::query_node(y,r2,y2,x2);
    h1=y1;h2=y2;
    int lca=BT::LCA(x1,x2,h1,h2),r=CT::right[lca].root;
    dist=ST::dis(r1,y1)+ST::dis(r2,y2)-ST::dis_lca(h1,h2,r)*2+BT::dist(x1,x2,lca);
    printf("%lld\n",dist);
}
void work(){
    long long x,y;
    while(q--){
        x=read();y=read();
        solve(x,y);
    }
}
void init(){
    int x,y,rt;
    n=read();m=read();q=read();
    for(int i=1;i<n;i++){
        x=read();y=read();
        ST::add(x,y);
    }
    ST::deep[1]=1;
    ST::buildtree(1);
    ST::step();
    CT::buildtree();
    CT::insert_node(1,c++);
    for(int i=1;i<=m;i++){
        int u=read();
        long long v=read();
        CT::query_node(v,rt,y,x);
        CT::insert_node(u,c);
        BT::val[c]=y;
        int w=ST::dis(y,rt)+1;
        BT::add(x,c,w);
        c++;
    }
    BT::deep[1]=1;BT::dis[1]=0;
    BT::buildtree(1);
    BT::step();
}
int main(){
    init();
    work();
    return 0;
}