Description:

给定一颗n个点的树，有m个询问，求任意两点路径上点权第k小的点

Hint：

\(n,m<=1e5\)

Solution:

比较水
以每个点到根节点的数的前缀和建主席树
结合树上两点距离求法
每次的\(size=size[u]+size[v]-size[lca]-size[fa[lca]]\)

#include<bits/stdc++.h>
using namespace std;
const int mxn=6e5+5;
struct ed {
    int to,nxt;
}t[mxn<<1];
int n,m,s,tot,ans,cnt,hd[mxn],f[mxn][19],ls[mxn<<3],rs[mxn<<3],sum[mxn<<3],a[mxn],b[mxn],rt[mxn],dep[mxn];

inline void add(int u,int v) {
    t[++cnt]=(ed){v,hd[u]},hd[u]=cnt;
}

void update(int las,int& p,int l,int r,int val)
{
    if(!p) p=++tot;
    sum[p]=sum[las]+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(val<=mid) update(ls[las],ls[p],l,mid,val),rs[p]=rs[las];
    else update(rs[las],rs[p],mid+1,r,val),ls[p]=ls[las];
}

int query(int las1,int las2,int p1,int p2,int l,int r,int k)
{
    if(l==r) return l;
    int tp=sum[ls[p1]]+sum[ls[p2]]-sum[ls[las1]]-sum[ls[las2]];
    int mid=(l+r)>>1;
    if(k<=tp) query(ls[las1],ls[las2],ls[p1],ls[p2],l,mid,k);
    else query(rs[las1],rs[las2],rs[p1],rs[p2],mid+1,r,k-tp);
}

void dfs(int u,int fa)
{
    f[u][0]=fa; dep[u]=dep[fa]+1;
    update(rt[fa],rt[u],1,s,b[u]);
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        dfs(v,u);
    }
}

int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=18;i>=0;--i) 
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
    if(x==y) return x;
    for(int i=18;i>=0;--i)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];     
}

void solve(int u,int v,int k) 
{
    u^=ans;
    int lca=LCA(u,v); 
    ans=a[query(rt[lca],rt[f[lca][0]],rt[u],rt[v],1,s,k)];
    printf("%d\n",ans);
}

int main()
{
    scanf("%d%d",&n,&m); int u,v,k;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
    sort(a+1,a+n+1);
    s=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;++i) b[i]=lower_bound(a+1,a+s+1,b[i])-a;
    for(int i=1;i<n;++i) {
        scanf("%d%d",&u,&v);
        add(u,v); add(v,u);
    }
    dfs(1,0);
    for(int j=1;j<=18;++j) 
        for(int i=1;i<=n;++i) 
            f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=m;++i) {
        scanf("%d%d%d",&u,&v,&k);
        solve(u,v,k);
    }
    return 0;
}

[SP10628]Count on a tree

原文：https://www.cnblogs.com/list1/p/10364189.html