洛谷 - P2633 Count on a tree

传送门：洛谷 - P2633

思路分析

跟求区间第k小一样的思路
树上差分: sum[u–>v] = sum[u] + sum[v] - sum[lca$(u,v)$] -sum[fa[lca$(u,v)$]]

样例输入

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

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <chrono>
#include <random>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

struct node {
    int l,r,sum;
} tree[N*40];

vector<int>e[N*2],b;
int cnt,root[N],a[N],n,m,tot;
int fa[N],dep[N],son[N],siz[N],top[N];

void ins(int l,int r,int pre,int &now,int pos) {
    tree[++cnt]=tree[pre];
    now=cnt;
    tree[now].sum++;
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) ins(l,mid,tree[pre].l,tree[now].l,pos);
    else ins(mid+1,r,tree[pre].r,tree[now].r,pos);
}

int query(int l,int r,int u,int v,int l_ca,int lcafa,int k) {
    if(l==r) return l;
    int mid=l+r>>1;
    int temp=tree[tree[u].l].sum+tree[tree[v].l].sum-tree[tree[l_ca].l].sum-tree[tree[lcafa].l].sum;
    if(k<=temp) return query(l,mid,tree[u].l,tree[v].l,tree[l_ca].l,tree[lcafa].l,k);
    else return query(mid+1,r,tree[u].r,tree[v].r,tree[l_ca].r,tree[lcafa].r,k-temp);
}

int getid(int x) {
    return lower_bound(all(b),x)-b.begin()+1;
}

void dfs1(int u,int f) {
    fa[u]=f;
    dep[u]=dep[f]+1;
    siz[u]=1;
    int maxsize=-1;
    for(auto v:e[u]) {
        if(v==f)continue;
        ins(1,tot,root[u],root[v],getid(a[v]));
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>maxsize) {
            son[u]=v;
            maxsize=siz[v];
        }
    }
}

void dfs2(int u,int t) {
    top[u]=t;
    if(!son[u])
        return ;
    dfs2(son[u],t);
    for(auto v:e[u]) {
        if(v==son[u]||v==fa[u])
            continue;
        dfs2(v,v);
    }
}

int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])    swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]>dep[y]?y:x;
}



int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i],b.push_back(a[i]);
    for(int i=1; i<n; i++) {
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    sort(all(b));
    b.erase(unique(all(b)),b.end());
    tot=b.size();
    ins(1,tot,root[0],root[1],getid(a[1]));
    dfs1(1,0);
    dfs2(1,0);
    int last=0;
    while(m--) {
        int u,v,k;
        cin>>u>>v>>k;
        u^=last;
        int lc=lca(u,v);
        int ans=b[query(1,tot,root[u],root[v],root[lc],root[fa[lc]],k)-1];
        cout<<ans<<endl;
        last=ans;
    }




    return 0;
}