P2633 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行，表示每个询问的答案。

输入输出样例

输入样例#1：

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

0 5 2

10 5 3

11 5 4

110 8 2

输出样例#1：

说明

HINT：

N,M<=100000

暴力自重。。。

来源：bzoj2588 Spoj10628.

本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。

思路：主席树+LCA

以点的dfs序为下标，以点权为区间建立主席树

以前做过的主席树在序列上，所以是以前一个节点的线段树为基准建立的

这里在树上，所以可以考虑以根为基准建立线段树

u，v间增加的点数=cnt[u]+cnt[v]-cnt[LCA(u,v)]-cnt[father[LCA(u,v)]]

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 100001

using namespace std;

int n,m,tot,cnt,num,lastans;

int a[MAXN],ha[MAXN],root[MAXN];

int to[MAXN*],net[MAXN*],head[MAXN*];

int top[MAXN],dad[MAXN],deep[MAXN],size[MAXN];

struct nond{

    int l,r,cnt;

}tree[MAXN*];

void add(int u,int v){

    to[++tot]=v;net[tot]=head[u];head[u]=tot;

    to[++tot]=u;net[tot]=head[v];head[v]=tot;

}

void insert(int pre,int &now,int l,int r,int k){

    tree[now=++num].cnt=tree[pre].cnt+;

    if(l==r)    return ;

    int mid=(l+r)/;

    if(k<=mid){

        tree[now].r=tree[pre].r;

        insert(tree[pre].l,tree[now].l,l,mid,k);

    }

    else{

        tree[now].l=tree[pre].l;

        insert(tree[pre].r,tree[now].r,mid+,r,k);

    }

}

int query(int x,int y,int LCA,int fa_LCA,int l,int r,int k){

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

    int mid=(l+r)/;

    int tmp=tree[tree[x].l].cnt+tree[tree[y].l].cnt-tree[tree[LCA].l].cnt-tree[tree[fa_LCA].l].cnt;

    if(k<=tmp)    query(tree[x].l,tree[y].l,tree[LCA].l,tree[fa_LCA].l,l,mid,k);

    else    query(tree[x].r,tree[y].r,tree[LCA].r,tree[fa_LCA].r,mid+,r,k-tmp);

}

void dfs(int now){

    size[now]=;

    insert(root[dad[now]],root[now],,cnt,ha[now]);

    deep[now]=deep[dad[now]]+;

    for(int i=head[now];i;i=net[i])

        if(dad[now]!=to[i]){

            dad[to[i]]=now;

            dfs(to[i]);

            size[now]+=size[to[i]];

        }

}

void dfs1(int x){

    int t=;

    if(top[x]==)    top[x]=x;

    for(int i=head[x];i;i=net[i])

        if(dad[x]!=to[i]&&size[to[i]]>size[t])

            t=to[i];

    if(t){

        top[t]=top[x];

        dfs1(t);

    }

    for(int i=head[x];i;i=net[i])

        if(dad[x]!=to[i]&&t!=to[i])

            dfs1(to[i]);

}

int lca(int x,int y){

    for(;top[x]!=top[y];){

        if(deep[top[x]]<deep[top[y]])

            swap(x,y);

        x=dad[top[x]];

    }

    if(deep[x]>deep[y])

        swap(x,y);

    return x;

}

int main(){

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

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

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

        ha[i]=a[i];

    }

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

        int u,v;

        scanf("%d%d",&u,&v);

        add(u,v);

    }

    sort(a+,a++n);

    cnt=unique(a+,a++n)-(a+);

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

        ha[i]=lower_bound(a+,a++cnt,ha[i])-a;

    dfs();

    dfs1();

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

        int u,v,k;

        scanf("%d%d%d",&u,&v,&k);

        u^=lastans;

        int LCA=lca(u,v);

        lastans=query(root[u],root[v],root[LCA],root[dad[LCA]],,cnt,k);

        if(i!=m)    cout<<lastans<<endl;

        else cout<<lastans;

    }

}

巴特西

洛谷 P2633 Count on a tree

P2633 Count on a tree

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章