Count on a tree

题目描述

给定一棵\(N\)个节点的树，每个点有一个权值，对于\(M\)个询问\((u,v,k)\)，你需要回答\(u\) \(xor\) \(lastans\)和\(v\)这两个节点间第\(K\)小的点权。其中\(lastans\)是上一个询问的答案，初始为\(0\)，即第一个询问的u是明文。

输入输出格式

输入格式：

第一行两个整数\(N,M\)。

第二行有\(N\)个整数，其中第\(i\)个整数表示点\(i\)的权值。

后面\(N-1\)行每行两个整数\((x,y)\)，表示点\(x\)到点\(y\)有一条边。

最后\(M\)行每行两个整数\((u,v,k)\)，表示一组询问。

输出格式：

\(M\)行，表示每个询问的答案。

一看是无修改的第\(k\)值查询，我们可以用可持久化降维。

就是把序列上的第\(k\)值扩展到了树上。

我们考虑一条树上路径可以被怎么表示

这样类比，假设树上每个点有点权，则树上路径点权之和可以被树的前缀和数组这样表示
\(len(u,v)=dis[u]+dis[v]-dis[lca(u,v)]-dis[father(lca[u,v])]\)

然而前缀和其实就是一维的可持久化，我们把\(dis\)数组类比成主席树加加减减就好了

Code:

#include 
#include 
#define ls ch[now][0]
#define rs ch[now][1]
const int N=100010;
int Next[N<<1],to[N<<1],head[N],cnt;
void add(int u,int v)
{
    Next[++cnt]=head[u];to[cnt]=v;head[u]=cnt;
}
int sum[N*25],ch[N*25][2],tot,n,m,n_;
void updata(int now)
{
    sum[now]=sum[ls]+sum[rs];
}
int rebuild(int las,int l,int r,int pos)
{
    int now=++tot;
    if(l==r)
    {
        sum[now]=sum[las]+1;
        return now;
    }
    int mid=l+r>>1;
    if(pos<=mid)
    {
        ls=rebuild(ch[las][0],l,mid,pos);
        rs=ch[las][1];
    }
    else
    {
        ls=ch[las][0];
        rs=rebuild(ch[las][1],mid+1,r,pos);
    }
    updata(now);
    return now;
}
int ha[N],loc[N],root[N];
int query(int u,int v,int lca,int lcaf,int l,int r,int k)
{
    if(l==r) return ha[l];
    int s=sum[ch[u][0]]+sum[ch[v][0]]-sum[ch[lca][0]]-sum[ch[lcaf][0]];
    int mid=l+r>>1;
    if(k<=s) return query(ch[u][0],ch[v][0],ch[lca][0],ch[lcaf][0],l,mid,k);
    else return query(ch[u][1],ch[v][1],ch[lca][1],ch[lcaf][1],mid+1,r,k-s);
}
int top[N],dfn[N],f[N],dep[N],ws[N],siz[N],time;
void dfs1(int now)
{
    root[now]=rebuild(root[f[now]],1,n,loc[now]);
    siz[now]++;
    for(int i=head[now];i;i=Next[i])
    {
        int v=to[i];
        if(v!=f[now])
        {
            f[v]=now;
            dep[v]=dep[now]+1;
            dfs1(v);
            siz[now]+=siz[v];
            if(siz[ws[now]]dep[top[y]])
            x=f[top[x]];
        else
            y=f[top[y]];
    }
    return dep[x] node[N];
void init()
{
    scanf("%d%d",&n_,&m);
    for(int d,i=1;i<=n_;i++)
    {
        scanf("%d",&d);
        node[i]=std::make_pair(d,i);
    }
    std::sort(node+1,node+1+n_);
    for(int i=1;i<=n_;i++)
    {
        if(node[i].first!=node[i-1].first) n++;
        ha[n]=node[i].first;
        loc[node[i].second]=n;
    }
    for(int u,v,i=1;i