本文共 1558 字，大约阅读时间需要 5 分钟。
题目大意
给一棵有点权的n个点的有根树，保证任意两点的点权不同，m次询问每次询问x的子树中权值第k大的点。
输入
先输入n，然后每个点点权，再输入n-1行每行两个数x,y代表x和y相连，再输入m，之后m次询问，每行两个数x,k。
主席树，随便找一个点为根，再dfs出树的dfs序，按dfs序建每一时刻主席树，利用主席树查询x子树区间第k大。
#include #include #include #include #include #include #include #include #include #include using namespace std;inline char _read(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int read(){ int x=0,f=1;char ch=_read(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=_read();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=_read();} return x*f;}int n,m;int x,y;int tot;int num;int cnt;int q[100010];int s[100010];int t[100010];int v[100010];int to[200010];int ls[4000010];int rs[4000010];int next[200010];int head[100010];int root[100010];int sum[4000010];map b;void add(int x,int y){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y;}void dfs(int x,int fa){ s[x]=++num; q[num]=x; for(int i=head[x];i;i=next[i]) { if(to[i]!=fa) { dfs(to[i],x); } } t[x]=num;}int updata(int pre,int l,int r,int v){ int rt=++cnt; if(l==r) { sum[rt]=sum[pre]+1; return rt; } ls[rt]=ls[pre]; rs[rt]=rs[pre]; sum[rt]=sum[pre]+1; int mid=(l+r)>>1; if(v<=mid) { ls[rt]=updata(ls[pre],l,mid,v); } else { rs[rt]=updata(rs[pre],mid+1,r,v); } return rt;}int query(int x,int y,int l,int r,int k){ if(l==r) { return b[l]; } int val=sum[ls[y]]-sum[ls[x]]; int mid=(l+r)>>1; if(val
转载于:https://www.cnblogs.com/Khada-Jhin/p/9449809.html