标题效果：两棵树之间的首次查询k大点的权利。

思维：树木覆盖树，事实上，它是正常的树木覆盖了持久段树。

由于使用权值段树可以寻求区间k大，然后应用到持久段树思想，间隔可以做减法。详见代码。

CODE：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define MAX 100010#define NIL (tree[0])using namespace std;pair
         
           src[MAX];struct Complex{	Complex *son[2];	int cnt;	Complex(Complex *_,Complex *__,int ___):cnt(___) {		son[0] = _;		son[1] = __;	}	Complex() {}}*tree[MAX];int points,asks;int xx[MAX];int head[MAX],total;int next[MAX << 1],aim[MAX << 1];int father[MAX][20],deep[MAX];inline void Add(int x,int y);void DFS(int x);void SparseTable();Complex *BuildTree(Complex *pos,int x,int y,int val);int GetAns(Complex *l,Complex *r,Complex *f,Complex *p,int x,int y,int k);int GetLCA(int x,int y);int Ask(int x,int y,int k);int main(){	cin >> points >> asks;	for(int i = 1;i <= points; ++i)		scanf("%d",&src[i].first),src[i].second = i;	sort(src + 1,src + points + 1);	for(int i = 1;i <= points; ++i)		xx[src[i].second] = i;	for(int x,y,i = 1;i < points; ++i) {		scanf("%d%d",&x,&y);		Add(x,y),Add(y,x);	}	NIL = new Complex(NULL,NULL,0);	NIL->son[0] = NIL->son[1] = NIL;	DFS(1);	SparseTable();	int now = 0;	for(int x,y,k,i = 1;i <= asks; ++i) {		scanf("%d%d%d",&x,&y,&k);		printf("%d",now = src[Ask(x ^ now,y,k)].first);		if(i != asks)	puts("");	}	return 0;}inline void Add(int x,int y){	next[++total] = head[x];	aim[total] = y;	head[x] = total;}void DFS(int x){	deep[x] = deep[father[x][0]] + 1;	tree[x] = BuildTree(tree[father[x][0]],1,points,xx[x]);	for(int i = head[x];i;i = next[i]) {		if(aim[i] == father[x][0])	continue;		father[aim[i]][0] = x;		DFS(aim[i]);	}}void SparseTable(){	for(int j = 1;j <= 19; ++j)		for(int i = 1;i <= points; ++i)			father[i][j] = father[father[i][j - 1]][j - 1];}int Ask(int x,int y,int k){	int lca = GetLCA(x,y);	return GetAns(tree[x],tree[y],tree[lca],tree[father[lca][0]],1,points,k);}Complex *BuildTree(Complex *pos,int x,int y,int val){	int mid = (x + y) >> 1;	if(x == y)	return new Complex(NIL,NIL,pos->cnt + 1);	if(val <= mid)	return new Complex(BuildTree(pos->son[0],x,mid,val),pos->son[1],pos->cnt + 1);	return new Complex(pos->son[0],BuildTree(pos->son[1],mid + 1,y,val),pos->cnt + 1);	}int GetLCA(int x,int y){	if(deep[x] < deep[y])	swap(x,y);	for(int i = 19; ~i; --i)		if(deep[father[x][i]] >= deep[y])			x = father[x][i];	if(x == y)	return x;	for(int i = 19; ~i; --i)		if(father[x][i] != father[y][i])			x = father[x][i],y = father[y][i];	return father[x][0];}int GetAns(Complex *l,Complex *r,Complex *f,Complex *p,int x,int y,int k){	if(x == y)	return x;	int mid = (x + y) >> 1;	int temp = l->son[0]->cnt + r->son[0]->cnt - f->son[0]->cnt - p->son[0]->cnt;	if(k <= temp)	return GetAns(l->son[0],r->son[0],f->son[0],p->son[0],x,mid,k);	return GetAns(l->son[1],r->son[1],f->son[1],p->son[1],mid + 1,y,k - temp);}
         
        
       
      
     

版权声明：本文博客原创文章。博客，未经同意，不得转载。