主席树的入门题目,这道题的题意其实就是说,给你一棵树,询问在两个节点之间的路径上的区间第K小

我们如何把树上问题转换为区间问题呢?

其实DFS就可以,我们按照DFS的顺序,对线段树进行建树,那么这个树上问题就可以转换为区间问题了,

那么如何询问来表示两个节点之间的路径呢?

其实也很简单,可以看看以下的图。。。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#define LL long long
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define pb push_back
using namespace std;
const int maxx = ;
struct node{
int l,r,cnt;
}tree[maxx*];
inline int MID(int l,int r){return (l+r)>>;};
int root[maxx*];
int a[maxx];
int ver[maxx*],Next[maxx*],head[maxx];
int tot,cnt,n,m;
int t=;
int fa[maxx],p[maxx][],deepth[maxx];
vector<int>v;
void add(int x,int y){
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
ver[++tot]=x;Next[tot]=head[y];head[y]=tot;
}
void update(int l,int r,int pre,int &now,int pos){
now=++cnt;
tree[now]=tree[pre];
tree[now].cnt++;
if (l==r)return;
int mid=(l+r)>>;
if (pos<=mid)
update(l,mid,tree[pre].l,tree[now].l,pos);
else
update(mid+,r,tree[pre].r,tree[now].r,pos);
}
int query(int l,int r,int L,int R,int k,int lca,int flac){
if (l==r)return l;
int tmp=tree[tree[R].l].cnt+tree[tree[L].l].cnt-tree[tree[lca].l].cnt-tree[tree[flac].l].cnt;
int mid=MID(l,r);
if (k<=tmp)
return query(l,mid,tree[L].l,tree[R].l,k,tree[lca].l,tree[flac].l);
else
return query(mid+,r,tree[L].r,tree[R].r,k-tmp,tree[lca].r,tree[flac].r);
}
void dfs(int u,int pre){
fa[u]=pre;
deepth[u]=deepth[pre]+;
p[u][]=pre;
update(,n,root[pre],root[u],a[u]);
rep(i,,)p[u][i]=p[p[u][i-]][i-];
for (int i=head[u];i;i=Next[i]){
int y=ver[i];
if (y==pre)continue;
dfs(y,u);
}
}
int LCA(int x,int y){
if (deepth[x]>deepth[y])swap(x,y);
per(i,t,){
if (deepth[p[y][i]]>=deepth[x])y=p[y][i];
}
if (x==y)return y;
per(i,t,){
if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];
}
return p[x][];
}
int main(){
while(~scanf("%d%d",&n,&m)){
int uu,vv;
memset(head,,sizeof(head));
rep(i,,n){
scanf("%d",&a[i]);
v.pb(a[i]);
}
tot=;
cnt=;
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
rep(i,,n-){
scanf("%d%d",&uu,&vv);
add(uu,vv);
}
rep(i,,n){
a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+;
}
dfs(,);
int k;
while(m--){
scanf("%d%d%d",&uu,&vv,&k);
int lca=LCA(uu,vv);
printf("%d\n",v[query(,n,root[uu],root[vv],k,root[lca],root[fa[lca]])-]);
}
}
return ;
}

最新文章

  1. Android local.properties 文件读取
  2. vtkBoxWidget2Example
  3. [普通平衡树splay]【学习笔记】
  4. UVa815_Flooded!
  5. 动态执行C#代码
  6. c语言开源项目--SQLite学习资料总结
  7. 转:SSE:服务器发送事件
  8. 加快maven中jar包的下载速度
  9. SVN库迁移
  10. noip第25课资料
  11. MapRedcue的demo(协同过滤)
  12. springboot maven 部署
  13. 在ASP.NET MVC中使用Area区域
  14. 数字转换大写人民币的delphi实现
  15. 清明 DAY 1
  16. securecrt8注册码
  17. 基本数据结构:链表(list)
  18. Android-上下文菜单Menu
  19. Mac 10.12安装hosts快速切换工SwitchHosts!
  20. windows C++ new/delete内存大小

热门文章

  1. day38 02-Spring快速入门
  2. BZOJ2529: [Poi2011]Sticks
  3. 关于502 bad gateway报错的解决办法
  4. 第十章—DOM(0)—NODE类型
  5. IDG资本全球拼图:近10年揽26家独角兽,最敢出手VC再造&quot;VC+&quot;
  6. 【JZOJ3215】【SDOI2013】费用流
  7. DirectX11笔记(九)--Direct3D渲染5--CONSTANT BUFFERS
  8. LintCode_69 二叉树前序遍历
  9. java通过实体类组装报文
  10. java 使用poi导出Excel,设置单元格保护不可编辑