洛谷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行，表示每個詢問的答案。

輸入輸出樣例

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

2
8
9
105
7

說明

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;
}