技术教程 编程教程 SPOJ 10628 Count on a tree（Tarjan离线LCA+主席树求树上第K小） 正文

SPOJ 10628 Count on a tree（Tarjan离线LCA+主席树求树上第K小）

2023-04-20,,

COT - Count on a tree

#tree

You are given a tree with N nodes.The tree nodes are numbered from 1 to N.Each node has an integer weight.

We will ask you to perform the following operation:

u v k : ask for the kth minimum weight on the path from node u to node v

Input

In the first line there are two integers N and M.(N,M<=100000)

In the second line there are N integers.The ith integer denotes the weight of the ith node.

In the next N-1 lines,each line contains two integers u v,which describes an edge (u,v).

In the next M lines,each line contains three integers u v k,which means an operation asking for the kth minimum weight on the path from node u to node v.

Output

For each operation,print its result.

Example

Input:

8 5

8 5

105 2 9 3 8 5 7 7

1 2

1 3

1 4

3 5

3 6

3 7

4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2 
Output:

2
8
9
105
7 

Submit solution!

 

题目链接：SPOJ 10628

做了一个晚上无奈网上绝大部分都是用在线RMQ-ST做的，Tarjan离线的少之又少，而且找到的几份Tarjan的也是另外一种方法好像是求深度的，渣渣我不会只会普通的query加边求LCA，那些AC代码真是写的惨不忍睹，变量名字起的根本无法直视也没有基本的缩进，水平不够又看不懂只好拿来跑对拍了。。想想RMQ-ST求LCA又不会，肯定是只能死磕Tarjan了。

先说一下如何建树，一般的主席树是在线性结构上建立的，其实树形结构是线性结构的拓展，任何一条链都是可以看成线性结构，那也就是说原本建树是在arr[i-1]的基础上，在树形结构里显然就是在父亲的基础上建树，显然一个根节点出来的一颗前缀可能被多个儿子继承。因此我是又用一个简单的DFS一路上进行向下建树，其实建树应该是可以合并到Tarjan里去的，只是DFS这样写起来比较清晰。

然后每一次查询就是U->V这一段中的所有点，根据树中LCA的性质有：$cnt_{u-v}=cnt[u]+cnt[v]-2*cnt[LCA(u,v)]$，但是这样可能会存在一些问题，由于前缀的性质prefix[R]-prefix[L]=total[L-1,R]，因此这样一来LCA这个点就都被减掉了没有算在里面，但是其实路径上是包含LCA这个点的，那么这个式子需要稍微变形一下，左边的把LCA减掉，右边的把LCA留下，这样刚好凑到一条路且没有点重复，理解起来也比那些判断LCA点值来加减cnt来的简单明了，没有输入外挂1.21s跑完还行…………

即：  $cnt_{u-v}=cnt[u]+cnt[v]-cnt[LCA(u,v)]-cnt[F_{LCA}(u,v)]$，但是这条式子却不是写起来这么简单，为了这个debug了一个早上，最后发现是传入的F_LCA有问题，试想我们的root是根据不同的左右孩子编号进行识别的，显然跟LCA的点没有关系，但father数组是根据点来映射父亲的，因此不能在递归的时候传原树中LCA的父亲，这样从第二层开始就是错的，应该用LCA的父亲所在的root编号进行传递，这样一来从头到尾用的都是主席树里的节点了…………，最后记得离散化回去，不然答案很奇怪

代码：

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=100010;

struct edge

{

    int to;

    int nxt;

};

struct query

{

    int to;

    int nxt;

    int id;

};

struct info

{

    int l,r,lca,k;

};

struct seg

{

    int lson,rson;

    int cnt;

};

seg T[N*40];

info q[N];

query Q[N<<1];

edge E[N<<1];

int head[N],rhead[N],tot,rtot;

int vis[N],pre[N],ances[N];

int order,arr[N],father[N],root[N],rt_cnt,n;

vector<int>vec;

void init()

{

    CLR(head,-1);

    CLR(rhead,-1);

    tot=0;

    rtot=0;

    CLR(vis,0);

    for (int i=0; i<N; ++i)

    {

        pre[i]=i;

        T[i].cnt=T[i].lson=T[i].rson=0;

    }

    CLR(ances,0);

    CLR(father,0);

    order=0;

    CLR(root,0);

    rt_cnt=0;

    vec.clear();

}

inline void add(int s,int t)

{

    E[tot].to=t;

    E[tot].nxt=head[s];

    head[s]=tot++;

}

inline void addQ(int s,int t,int id)

{

    Q[rtot].id=id;

    Q[rtot].to=t;

    Q[rtot].nxt=rhead[s];

    rhead[s]=rtot++;

}

int Find(int n)

{

    if(pre[n]==n)

        return n;

    return pre[n]=Find(pre[n]);

}

void update(int &cur,int ori,int l,int r,int pos)

{

    cur=++rt_cnt;

    T[cur]=T[ori];

    ++T[cur].cnt;

    if(l==r)

        return ;

    int mid=MID(l,r);

    if(pos<=mid)

        update(T[cur].lson, T[ori].lson, l, mid, pos);

    else

        update(T[cur].rson, T[ori].rson, mid+1, r, pos);

}

int query(int U,int V,int LCA,int F_LCA,int l,int r,int k,int c)

{

    if(l==r)

        return l;

    int mid=MID(l,r);

    int cnt=T[T[U].lson].cnt+T[T[V].lson].cnt-T[T[LCA].lson].cnt-T[T[F_LCA].lson].cnt;

    if(k<=cnt)

        return query(T[U].lson,T[V].lson,T[LCA].lson,T[F_LCA].lson,l,mid,k,c);

    else

        return query(T[U].rson,T[V].rson,T[LCA].rson,T[F_LCA].rson,mid+1,r,k-cnt,c);

}

void Tarjan(int u)

{

    vis[u]=1;

    ances[u]=u;

    int i,v;

    for (i=head[u]; ~i; i = E[i].nxt)

    {

        v = E[i].to;

        if(!vis[v])

        {

            Tarjan(v);

            pre[v]=u;

            ances[Find(u)]=u;

        }

    }

    for (i=rhead[u]; ~i; i = Q[i].nxt)

    {

        v = Q[i].to;

        if(vis[v])

            q[Q[i].id].lca=ances[Find(v)];

    }

}

void dfs_build(int u,int fa)

{

    update(root[u],root[fa],1,n,arr[u]);

    father[u]=fa;

    for (int i=head[u]; ~i; i = E[i].nxt)

    {

        int v=E[i].to;

        if(v!=fa)

            dfs_build(v,u);

    }

}

int main(void)

{

    int m,a,b,i;

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

    {

        init();

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

        {

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

            vec.push_back(arr[i]);

        }

        sort(vec.begin(),vec.end());

        vec.erase(unique(vec.begin(),vec.end()),vec.end());

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

            arr[i]=lower_bound(vec.begin(),vec.end(),arr[i])-vec.begin()+1;

        for (i=0; i<n-1; ++i)

        {

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

            add(a,b);

            add(b,a);

        }

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

        {

            scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);

            q[i].lca=0;

            addQ(q[i].l,q[i].r,i);

            addQ(q[i].r,q[i].l,i);

        }

        Tarjan(1);

        dfs_build(1,0);

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

        {

            int indx=query(root[q[i].l],root[q[i].r],root[q[i].lca],root[father[q[i].lca]],1,n,q[i].k,arr[q[i].lca]);

            printf("%d\n",vec[indx-1]);//vec里下标从是0开始的，而我把arr还是设为从1开始，因此要减一

        }

    }

    return 0;

}

趁寒假有空膜了一下ST在线的LCA算法，挺方便的代码量也小，就是时间稍慢一点

代码：

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 100010;

struct edge

{

    int to;

    int nxt;

};

struct info

{

    int l, r, lca, k;

};

struct seg

{

    int lson, rson;

    int cnt;

};

seg T[N * 40];

info q[N];

edge E[N << 1];

int head[N], tot;

int arr[N], father[N], root[N], rt_cnt, n;

int ver[N << 1], dp[N << 1][20], D[N << 1], F[N], sz;

vector<int>vec;

bitset<N>vis;

void init()

{

    CLR(T, 0);

    CLR(head, -1);

    tot = 0;

    CLR(father, 0);

    CLR(root, 0);

    rt_cnt = 0;

    sz = 0;

    vec.clear();

    vis.reset();

}

void RMQ_init(int l, int r)

{

    int i, j;

    for (i = l; i <= r; ++i)

        dp[i][0] = i;

    for (j = 1; l + (1 << j) - 1 <= r; ++j)

    {

        for (i = l; i + (1 << j) - 1 <= r; ++i)

        {

            int a = dp[i][j - 1], b = dp[i + (1 << (j - 1))][j - 1];

            dp[i][j] = (D[a] < D[b] ? a : b);

        }

    }

}

int LCA(int u, int v)

{

    int l = F[u], r = F[v];

    if (l > r)

        swap(l, r);

    int k = log2(r - l + 1);

    int a = dp[l][k], b = dp[r - (1 << k) + 1][k];

    return D[a] <= D[b] ? ver[a] : ver[b];

}

inline void add(int s, int t)

{

    E[tot].to = t;

    E[tot].nxt = head[s];

    head[s] = tot++;

}

void update(int &cur, int ori, int l, int r, int pos)

{

    cur = ++rt_cnt;

    T[cur] = T[ori];

    ++T[cur].cnt;

    if (l == r)

        return ;

    int mid = MID(l, r);

    if (pos <= mid)

        update(T[cur].lson, T[ori].lson, l, mid, pos);

    else

        update(T[cur].rson, T[ori].rson, mid + 1, r, pos);

}

int query(int U, int V, int LCA, int F_LCA, int l, int r, int k)

{

    if (l == r)

        return l;

    int mid = MID(l, r);

    int cnt = T[T[U].lson].cnt + T[T[V].lson].cnt - T[T[LCA].lson].cnt - T[T[F_LCA].lson].cnt;

    if (k <= cnt)

        return query(T[U].lson, T[V].lson, T[LCA].lson, T[F_LCA].lson, l, mid, k);

    else

        return query(T[U].rson, T[V].rson, T[LCA].rson, T[F_LCA].rson, mid + 1, r, k - cnt);

}

void dfs_build(int u, int fa, int d)

{

    vis[u] = 1;

    ver[++sz] = u;

    F[u] = sz;

    D[sz] = d;

    update(root[u], root[fa], 1, n, arr[u]);

    father[u] = fa;

    for (int i = head[u]; ~i; i = E[i].nxt)

    {

        int v = E[i].to;

        if (!vis[v])

        {

            dfs_build(v, u, d + 1);

            ver[++sz] = u;

            D[sz] = d;

        }

    }

}

int main(void)

{

    int m, a, b, i;

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

    {

        init();

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

        {

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

            vec.push_back(arr[i]);

        }

        sort(vec.begin(), vec.end());

        vec.erase(unique(vec.begin(), vec.end()), vec.end());

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

            arr[i] = lower_bound(vec.begin(), vec.end(), arr[i]) - vec.begin() + 1;

        for (i = 0; i < n - 1; ++i)

        {

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

            add(a, b);

            add(b, a);

        }

        dfs_build(1, 0, 1);

        RMQ_init(1, sz);

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

        {

            scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);

            q[i].lca = LCA(q[i].l, q[i].r);

            int indx = query(root[q[i].l], root[q[i].r], root[q[i].lca], root[father[q[i].lca]], 1, n, q[i].k);

            printf("%d\n", vec[indx - 1]);

        }

    }

    return 0;

}

SPOJ 10628 Count on a tree（Tarjan离线LCA+主席树求树上第K小）的相关教程结束。

《SPOJ 10628 Count on a tree（Tarjan离线LCA+主席树求树上第K小）.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!