大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。
标题效果:两棵树之间的首次查询k大点的权利。
思维:树木覆盖树,事实上,它是正常的树木覆盖了持久段树。
由于使用权值段树可以寻求区间k大,然后应用到持久段树思想,间隔可以做减法。详见代码。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 100010 #define NIL (tree[0]) using namespace std; pair<int,int> 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); }
版权声明:本文博客原创文章。博客,未经同意,不得转载。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/117451.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...