E - Count on a tree 树上第K小
主席树的入门题目，这道题的题意其实就是说，给你一棵树，询问在两个节点之间的路径上的区间第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 = 100005; struct node{ int l,r,cnt; }tree[maxx*40]; inline int MID(int l,int r){return (l+r)>>1;}; int root[maxx*40]; int a[maxx]; int ver[maxx*2],Next[maxx*2],head[maxx]; int tot,cnt,n,m; int t=18; int fa[maxx],p[maxx][20],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)>>1; if (pos<=mid) update(l,mid,tree[pre].l,tree[now].l,pos); else update(mid+1,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+1,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]+1; p[u][0]=pre; update(1,n,root[pre],root[u],a[u]); rep(i,1,18)p[u][i]=p[p[u][i-1]][i-1]; 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,0){ if (deepth[p[y][i]]>=deepth[x])y=p[y][i]; } if (x==y)return y; per(i,t,0){ if(p[x][i]!=p[y][i])x=p[x][i],y=p[y][i]; } return p[x][0]; } int main(){ while(~scanf("%d%d",&n,&m)){ int uu,vv; memset(head,0,sizeof(head)); rep(i,1,n){ scanf("%d",&a[i]); v.pb(a[i]); } tot=1; cnt=0; sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); rep(i,1,n-1){ scanf("%d%d",&uu,&vv); add(uu,vv); } rep(i,1,n){ a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1; } dfs(1,0); int k; while(m--){ scanf("%d%d%d",&uu,&vv,&k); int lca=LCA(uu,vv); printf("%d\n",v[query(1,n,root[uu],root[vv],k,root[lca],root[fa[lca]])-1]); } } return 0; }
查看15道真题和解析
