caioj1443:第k小的数Ⅲ

【传送门：caioj1443】

简要题意：

　　给出一颗n个点的树，给出每个点的权值，再给出n-1条边，有m个询问，每个询问输入x,y,k，输出第x节点到第y节点的路径上第k大的点

题解：

　　这是一道主席树的例题，感觉很想用树链剖分，但是会超时吧......

　　做法就是将每个点到树的根所形成的链建立线段树，然后dfs找出点与点之间的父子关系，每个点都将自己和自己的父亲，自己的父亲的父亲....直到根所组成的所有线段树合并起来，然后就可以得到能够代表区间的主席树了，然后每当询问输入x,y时，就先找x和y的最近公共祖先（倍增LCA来求），然后x和y的路径其实就是x到根的路径加上y到根的路径，然后减去最近公共祖先到根的路径，再减去最近公共祖先的父亲到根的路径（为什么是最近公共祖先的父亲呢，因为如果是再减去最近公共祖先到根的路径的话，最近公共祖先就会被除去，这样是不对的，所以减去最近公共祖先的父亲到根的路径）

参考代码：

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int s[],ss[];

struct trnode

{

    int lc,rc,c;

}tr[];int cnt;

int rt[];

struct edge

{

    int x,y,next;

}a[];int len,last[];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int n;

int LS(int d)

{

    int l=,r=n,ans=;

    while(l<=r)

    {

        int mid=(l+r)/;

        if(s[mid]<=d)

        {

            ans=mid;

            l=mid+;

        }

        else r=mid-;

    }

    return ans;

}

void Link(int &u,int l,int r,int p)

{

    if(u==) u=++cnt;

    tr[u].c++;

    if(l==r) return ;

    int mid=(l+r)/;

    if(p<=mid) Link(tr[u].lc,l,mid,p);

    else Link(tr[u].rc,mid+,r,p);

}

void Merge(int &u1,int u2)

{

    if(u1==){u1=u2;return ;}

    if(u2==) return ;

    tr[u1].c+=tr[u2].c;

    Merge(tr[u1].lc,tr[u2].lc);

    Merge(tr[u1].rc,tr[u2].rc);

}

int dep[];

int f[][];

int LCA(int x,int y)

{

    if(dep[x]<dep[y]) swap(x,y);

    for(int i=;i>=;i--) if(dep[x]-dep[y]>=(<<i)) x=f[x][i];

    if(x==y) return x;

    for(int i=;i>=;i--)

        if(dep[x]>=(<<i)&&f[x][i]!=f[y][i])

        {

            x=f[x][i];y=f[y][i];

        }

    return f[x][];

}

void bt(int x,int fa)

{

    dep[x]=dep[fa]+;

    f[x][]=fa;

    for(int i=;(<<i)<=dep[x];i++) f[x][i]=f[f[x][i-]][i-];

    Merge(rt[x],rt[fa]);

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=fa)

        {

            bt(y,x);

        }

    }

}

int Ask(int u1,int u2,int u3,int u4,int l,int r,int p)

{

    if(l==r) return s[l];

    int c=tr[tr[u1].lc].c+tr[tr[u2].lc].c-tr[tr[u3].lc].c-tr[tr[u4].lc].c;

    int mid=(l+r)/;

    if(p<=c) return Ask(tr[u1].lc,tr[u2].lc,tr[u3].lc,tr[u4].lc,l,mid,p);

    else return Ask(tr[u1].rc,tr[u2].rc,tr[u3].rc,tr[u4].rc,mid+,r,p-c);

}

int main()

{

    int m;

    scanf("%d%d",&n,&m);

    cnt=;memset(rt,,sizeof(rt));

    for(int i=;i<=n;i++)

    {

        scanf("%d",&ss[i]);

        s[i]=ss[i];

    }

    sort(s+,s+n+);

    len=;memset(last,,sizeof(last));

    for(int i=;i<n;i++)

    {

        int x,y;

        scanf("%d%d",&x,&y);

        ins(x,y);ins(y,x);

    }

    cnt=;

    for(int i=;i<=n;i++) Link(rt[i],,n,LS(ss[i]));

    dep[]=;bt(,);

    for(int i=;i<=m;i++)

    {

        int x,y,k;

        scanf("%d%d%d",&x,&y,&k);

        int lca=LCA(x,y);

        printf("%d\n",Ask(rt[x],rt[y],rt[lca],rt[f[lca][]],,n,k));

    }

    return ;

}

巴特西

caioj1443:第k小的数Ⅲ

【传送门：caioj1443】

简要题意：

题解：

参考代码：

最新文章

热门文章