BZOJ2588 Count on a tree 【树上主席树】

2023-08-06 15:56:52

2588: Spoj 10628. Count on a tree

Time Limit: 12 Sec Memory Limit: 128 MB

Submit: 7577 Solved: 1852

[Submit][Status][Discuss]

Description

给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

Input

第一行两个整数N,M。

第二行有N个整数，其中第i个整数表示点i的权值。

后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。

最后M行每行两个整数(u,v,k)，表示一组询问。

Output

M行，表示每个询问的答案。最后一个询问不输出换行符

Sample Input

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

Sample Output

2

8

9

105

7

HINT

HINT：

N,M<=100000

暴力自重。。。

求区间第K大问题一般使用主席树

首先我们要了解主席树具有查询部分数据的功能，我们只要找出一种建树顺序，使得我们能通过区间加减拼凑出我们的目标序列

我们进行一次dfs，每个节点u以其father版本树建树，这样子每个节点所对应的主席树储存着该节点到根的数据

我们要得到u，v两点之间的数据，就rt[u] + rt[v] - rt[lca] - rt[fa[lca]]就好了【自己脑补】

【md调了两个小时原来是离散化出了错误，不知道为什么同种权值不能编一个号，求dalao解答QAQ】

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)

using namespace std;

const int maxn = 100005,maxm = 4000005,INF = 1000000000;

inline LL RD(){

	LL out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

	return out * flag;

}

int N,M,A[maxn],id[maxn],V[maxn],H[maxn],dep[maxn],fa[maxn][20],n = 0;

int siz = 0,rt[maxn],pos;

int head[maxn],nedge = 0;

struct EDGE{int to,next;}edge[2 * maxn];

struct node{LL sum;int ls,rs;}e[maxm];

inline void add(int u,int v){

	edge[nedge] = (EDGE){v,head[u]}; head[u] = nedge++;

	edge[nedge] = (EDGE){u,head[v]}; head[v] = nedge++;

}

inline bool cmp(const int& a,const int& b){return A[a] < A[b];}

void build(int& u,int pre,int l,int r){

	u = ++siz; e[u] = e[pre]; e[u].sum++;

	if (l == r) return;

	int mid = l + r >> 1;

	if (mid >= pos) build(e[u].ls,e[pre].ls,l,mid);

	else build(e[u].rs,e[pre].rs,mid + 1,r);

}

int Query(int r1,int r2,int r3,int r4,int l,int r,int k){

	if (l == r) return l;

	int mid = l + r >> 1,temp = e[e[r1].ls].sum + e[e[r2].ls].sum - e[e[r3].ls].sum - e[e[r4].ls].sum;

	if (temp >= k) return Query(e[r1].ls,e[r2].ls,e[r3].ls,e[r4].ls,l,mid,k);

	else return Query(e[r1].rs,e[r2].rs,e[r3].rs,e[r4].rs,mid + 1,r,k - temp);

}

inline int Lca(int u,int v){

	if (dep[u] < dep[v]) swap(u,v);

	int d = dep[u] - dep[v];

	for (int i = 0; (1 << i) <= d; i++)

		if ((1 << i) & d) u = fa[u][i];

	if (u == v) return u;

	for (int i = 19; i >= 0; i--)

		if (fa[u][i] != fa[v][i]) u = fa[u][i],v = fa[v][i];

	return fa[u][0];

}

void dfs(int u,int f,int d){

	fa[u][0] = f; pos = V[u]; dep[u] = ++d;

	build(rt[u],rt[f],1,n);

	Redge(u) if (edge[k].to != f) dfs(edge[k].to,u,d);

}

void init2(){REP(i,19) REP(u,N) fa[u][i] = fa[fa[u][i - 1]][i - 1];}

void init(){

	memset(head,-1,sizeof(head));

	N = RD(); M = RD();

	REP(i,N) A[i] = RD(),id[i] = i;

	REP(i,N - 1) add(RD(),RD());

	sort(id + 1,id + 1 + N,cmp);

	V[id[1]] = ++n; H[n] = A[id[1]];

	for (int i = 2; i <= N; i++) V[id[i]] = ++n,H[n] = A[id[i]];

}

void solve(){

	int u,v,k,lca,last = 0;

	while (M--){

		u = last ^ RD(); v = RD(); k = RD(); lca = Lca(u,v);

		printf("%d",last = H[Query(rt[u],rt[v],rt[lca],rt[fa[lca][0]],1,n,k)]);

		if (M) printf("\n");

	}

}

int main(){

	init();

	dfs(1,0,0);

	init2();

	solve();

	return 0;

}

码农公寓