SPOJ-COT-Count on a tree(树上路径第K小，可持久化线段树)

时间：2023-03-09 18:38:42
SPOJ-COT-Count on a tree(树上路径第K小，可持久化线段树)

题意：

求树上A，B两点路径上第K小的数

分析：

同样是可持久化线段树，只是这一次我们用它来维护树上的信息。

我们之前已经知道，可持久化线段树实际上是维护的一个前缀和，而前缀和不一定要出现在一个线性表上。

比如说我们从一棵树的根节点进行DFS，得到根节点到各节点的距离dist[x]——这是一个根-x路径上点与根节点距离的前缀和。

利用这个前缀和，我们可以解决一些树上任意路径的问题，比如在线询问[a,b]点对的距离——答案自然是dist[a]+dist[b]-2*dist[lca(a,b)]。

同理，我们可以利用可持久化线段树来解决树上任意路径的问题。

DFS遍历整棵树，然后在每个节点上建立一棵线段树，某一棵线段树的“前一版本”是位于该节点父亲节点fa的线段树。

利用与之前类似的方法插入点权(排序离散)。那么对于询问[a,b]，答案就是root[a]+root[b]-root[lca(a,b)]-root[fa[lca(a,b)]]上的第k大。

// File Name: cot.cpp

// Author: Zlbing

// Created Time: 2013年10月09日 星期三 19时24分55秒

#include<iostream>

#include<string>

#include<algorithm>

#include<cstdlib>

#include<cstdio>

#include<set>

#include<map>

#include<vector>

#include<cstring>

#include<stack>

#include<cmath>

#include<queue>

using namespace std;

#define CL(x,v); memset(x,v,sizeof(x));

#define INF 0x3f3f3f3f

#define LL long long

#define REP(i,r,n) for(int i=r;i<=n;i++)

#define RREP(i,n,r) for(int i=n;i>=r;i--)

const int MAXN=1e5+;

const int POW=;

int num[MAXN],hash[MAXN];

int ls[MAXN*],rs[MAXN*];

int sum[MAXN*];

int root[MAXN];

vector<int> G[MAXN];

int d[MAXN];

int p[MAXN][POW];

int tot;

int f[MAXN];

void build(int l,int r,int& rt)

{

    rt=++tot;

    sum[rt]=;

    if(l>=r)return;

    int m=(l+r)>>;

    build(l,m,ls[rt]);

    build(m+,r,rs[rt]);

}

void update(int last,int p,int l,int r,int &rt)

{

    rt=++tot;

    ls[rt]=ls[last];

    rs[rt]=rs[last];

    sum[rt]=sum[last]+;

    if(l>=r)return ;

    int m=(l+r)>>;

    if(p<=m)update(ls[last],p,l,m,ls[rt]);

    else update(rs[last],p,m+,r,rs[rt]);

}

int query(int left_rt,int right_rt,int lca_rt,int lca_frt,int l,int r,int k)

{

    if(l>=r)return l;

    int m=(l+r)>>;

    int cnt=sum[ls[right_rt]]+sum[ls[left_rt]]-sum[ls[lca_rt]]-sum[ls[lca_frt]];

    if(k<=cnt)

        return query(ls[left_rt],ls[right_rt],ls[lca_rt],ls[lca_frt],l,m,k);

    else

        return query(rs[left_rt],rs[right_rt],rs[lca_rt],rs[lca_frt],m+,r,k-cnt);

}

void dfs(int u,int fa,int cnt)

{

    f[u]=fa;

    d[u]=d[fa]+;

    p[u][]=fa;

    for(int i=;i<POW;i++)p[u][i]=p[p[u][i-]][i-];

    update(root[fa],num[u],,cnt,root[u]);

    for(int i=;i<(int)G[u].size();i++)

    {

        int v=G[u][i];

        if(v==fa)continue;

        dfs(v,u,cnt);

    }

}

int lca(int a,int b)

{

    if(d[a]>d[b])a^=b,b^=a,a^=b;

    if(d[a]<d[b])

    {

        int del=d[b]-d[a];

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

            if(del&(<<i))b=p[b][i];

    }

    if(a!=b)

    {

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

        {

            if(p[a][i]!=p[b][i])

            {

                a=p[a][i],b=p[b][i];

            }

        }

        a=p[a][],b=p[b][];

    }

    return a;

}

int main()

{

        int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        REP(i,,n)

        {

            G[i].clear();

        }

        CL(d,);

        CL(p,);

        CL(f,);

        REP(i,,n)

        {

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

            hash[i]=num[i];

        }

        tot=;

        sort(hash+,hash++n);

        int cnt=unique(hash+,hash+n+)-hash-;

        REP(i,,n)

        {

            num[i]=lower_bound(hash+,hash+cnt+,num[i])-hash;

        }

        int a,b,c;

        REP(i,,n-)

        {

            scanf("%d%d",&a,&b);

            G[a].push_back(b);

            G[b].push_back(a);

        }

        build(,cnt,root[]);

        dfs(,,cnt);

        REP(i,,m)

        {

            scanf("%d%d%d",&a,&b,&c);

            int t=lca(a,b);

            int id=query(root[a],root[b],root[t],root[f[t]],,cnt,c);

            printf("%d\n",hash[id]);

        }

    }

    return ;

}

相关文章