洛谷P2633 Count on a tree

2018-02-10 20:13:51来源:cnblogs.com作者:自为风月马前卒人点击

分享

题目描述

给定一棵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 5105 2 9 3 8 5 7 71 21 31 43 53 63 74 82 5 10 5 210 5 311 5 4110 8 2
输出样例#1: 复制
2891057

说明

HINT:

N,M<=100000

暴力自重。。。

来源:bzoj2588 Spoj10628.

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

树上第$k$大问题

做法比较套路

首先对权值离散化。

然后对每个节点建主席树,从父亲那里拷贝历史版本

求LCA的话用树剖,顺便可以建主席树。

// luogu-judger-enable-o2// luogu-judger-enable-o2#include<iostream>#include<vector>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN=2*1e6+10;const int INF=1e8+10;inline char nc(){    static char buf[MAXN],*p1=buf,*p2=buf;    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;}inline int read(){    char c=nc();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}    return x*f;}struct Edge{    int u,v,nxt;}E[MAXN];int head[MAXN];int num=1;inline void AddEdge(int x, int y){    E[num].u = x;    E[num].v = y;    E[num].nxt = head[x];    head[x] = num++;}int a[MAXN], b[MAXN], N, M, root[MAXN], totnum;int deep[MAXN], son[MAXN], top[MAXN], fa[MAXN], tot[MAXN];struct node{    int ls, rs, w;}T[MAXN];void Insert(int pre,int &now,int ll,int rr,int val){    now=++totnum;    T[now].ls=T[pre].ls;T[now].rs=T[pre].rs;    T[now].w=T[pre].w+1;    if(ll==rr) return ;    int mid=ll+rr>>1;    if(val<=mid) Insert(T[pre].ls,T[now].ls,ll,mid,val);    else         Insert(T[pre].rs,T[now].rs,mid+1,rr,val);}void dfs1(int now, int f){    fa[now] = f;    Insert(root[f],root[now],1,N,a[now]);    tot[now] = 1;    int maxson=-1;    for(int i = head[now]; i != -1; i = E[i].nxt)    {        if(deep[E[i].v] == 0 && E[i].v != f)        {            deep[E[i].v] = deep[now] + 1;            dfs1(E[i].v, now);            tot[now] += tot[E[i].v];            if(tot[E[i].v]>maxson) maxson = tot[E[i].v],son[now] = E[i].v;        }    }}void dfs2(int now, int topf){    top[now] = topf;    if(!son[now]) return ;    dfs2(son[now], topf);    for(int i = head[now]; i != -1; i=E[i].nxt)        if(E[i].v != son[now] && E[i].v != fa[now])            dfs2(E[i].v, E[i].v);}int LCA(int x, int y){    while(top[x] != top[y])    {        if(deep[top[x]] < deep[top[y]]) swap(x,y);        x = fa[top[x]];    }    if(deep[x] > deep[y]) swap(x,y);    return x;}int Query(int x, int y, int lca, int falca, int ll, int rr, int k){    if(ll==rr) return ll;    int used=T[T[x].ls].w + T[T[y].ls].w - T[T[lca].ls].w - T[T[falca].ls].w;    int mid=ll+rr>>1;    if(k<=used) return Query(T[x].ls, T[y].ls, T[lca].ls, T[falca].ls, ll, mid, k);    else        return Query(T[x].rs, T[y].rs, T[lca].rs, T[falca].rs, mid+1, rr, k-used);}int main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    memset(head,-1,sizeof(head));    N = read(); M = read();    for(int i = 1; i<=N; i++) a[i] = b[i] = read();    sort(b+1, b+N+1);    int num = unique(b, b+N+1) - b - 1;    for(int i = 1; i<=N; i++) a[i]=lower_bound(b, b+N, a[i]) - b;    for(int i=1; i<=N-1; i++)    {        int x=read(), y=read();        AddEdge(x, y);        AddEdge(y, x);    }    deep[1] = 1;    dfs1(1, 0);    dfs2(1,1);    int lastans=0;    while(M--)    {        int x=read(),y=read(),k=read();        x=x^lastans;        int lca=LCA(x,y);        lastans=b[Query(root[x], root[y], root[lca], root[fa[lca]],1,N,k)];        printf("%d/n",lastans);    }    return 0;}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台