洛谷P2633 Count on a tree

@Pelom  November 6, 2019

题意

给出一棵带点权的树,$m$个询问,求$u \rightarrow v$路径上第$k$小的点权

数据范围:$n,m \le 100000$ [强制在线]

题解

树上静态区间第$k$小,使用主席树维护
序列上的主席树使用的是前缀和思想;那么自然,在树上的情况就要用到树上前缀和
建树的时候在其父节点的基础上拷贝
包含$u \rightarrow v$路径上的信息的应为$$T[u]+T[v]-T[lca(u,v)]-T[fa[lca(u,v)]]$$

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100000+10;
int n,m,u,v,w;
int a[N],b[N];
int cnt,tot,sz,ans;
int rt[N],head[N],fa[N],dep[N],siz[N],son[N],top[N];
struct node{
    int ls,rs,w;
} T[N<<5];
struct edge{
    int nxt,to;
} e[N<<1];
inline void add(int u,int v){
    e[++cnt]=(edge){head[u],v};
    head[u]=cnt;
}
void build(int& rt,int l,int r){
    rt=++sz;
    if(l==r){
        return ;
    }
    int mid=l+r>>1;
    build(T[rt].ls,l,mid);
    build(T[rt].rs,mid+1,r);
}
void update(int& rt,int fa,int l,int r,int p){
    T[++sz]=T[fa];
    rt=sz;
    T[rt].w++;
    if(l==r){
        return ;
    }
    int mid=l+r>>1;
    if(p<=mid)
        update(T[rt].ls,T[fa].ls,l,mid,p);
    else update(T[rt].rs,T[fa].rs,mid+1,r,p);
}
int query(int r1,int r2,int r3,int r4,int l,int r,int k){
    if(l==r){
        return l;
    }
    int p=T[T[r1].ls].w+T[T[r2].ls].w-T[T[r3].ls].w-T[T[r4].ls].w;
    int mid=l+r>>1;
    if(p>=k)
        return query(T[r1].ls,T[r2].ls,T[r3].ls,T[r4].ls,l,mid,k);
    else return query(T[r1].rs,T[r2].rs,T[r3].rs,T[r4].rs,mid+1,r,k-p);
}
void dfs1(int u){
    siz[u]=1;
    dep[u]=dep[fa[u]]+1;
    update(rt[u],rt[fa[u]],1,tot,a[u]);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u])
            continue;
        fa[v]=u;
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
            son[u]=v;
    }
}
void dfs2(int u,int t){
    top[u]=t;
    if(!son[u])
        return ;
    dfs2(son[u],t);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa[u] || v==son[u])
            continue;
        dfs2(v,v);
    }
}
inline int LCA(int x,int y){
    for(;top[x]!=top[y];){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    if(dep[x]>dep[y])
        swap(x,y);
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    for(int i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    sort(b+1,b+n+1);
    tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    build(rt[0],1,tot);
    dfs1(1);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        u^=ans;
        int lca=LCA(u,v);
        ans=b[query(rt[u],rt[v],rt[lca],rt[fa[lca]],1,tot,w)];
        printf("%d\n",ans);
    }
    return 0;
}

添加新评论