| WZJ的数据结构（十三） |
| 难度级别：D； 运行时间限制：1000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
给你一棵N个节点的有根树（根节点为1），每个节点有权值Vi。请回答Q个问题： 每次给你两个正整数x、k，请回答以x为根的子树（包括x节点）中第k小的权值是多少（若不存在第k小数，输出-1）？ |
|
输入
|
|
第一行为两个正整数N,Q。
接下来N-1行每行两个正整数ui、vi，表示有条从ui向vi的树边。 第N+1行为N个正整数Vi。 最后Q行每行两个正整数x、k。 |
|
输出
|
|
对于每次询问输出答案，若不存在第k小数，输出-1。
|
|
输入示例
|
|
6 12
1 2 1 3 2 4 3 6 3 5 1 2 1 3 2 1 1 5 2 2 3 4 1 1 1 2 1 3 1 4 1 6 3 3 3 2 5 1 6 1 |
|
输出示例
|
|
2
3 -1 1 1 1 2 3 2 1 2 1 |
|
其他说明
|
|
1<=N,M,Vi<=100000
1<=x,k<=N |
新学了线段树的合并，来try一发。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
inline int read() {
int x=,f=;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
int first[maxn],next[maxn<<],to[maxn<<],last[maxn],n,q,e,cnt;
void AddEdge(int u,int v) {
to[++e]=v;next[e]=first[u];first[u]=e;
to[++e]=u;next[e]=first[v];first[v]=e;
}
int ls[maxnode],rs[maxnode],sumv[maxnode],ToT;
void update(int& x,int l,int r,int pos) {
sumv[x=++ToT]=;if(l==r) return;
int mid=l+r>>;
if(pos<=mid) update(ls[x],l,mid,pos);
else update(rs[x],mid+,r,pos);
}
int merge(int x,int y) {
if(!x||!y) return max(x,y);
if(!ls[x]&&!rs[x]) sumv[x]+=sumv[y];
else {
ls[x]=merge(ls[x],ls[y]);rs[x]=merge(rs[x],rs[y]);
sumv[x]=sumv[ls[x]]+sumv[rs[x]];
}
return x;
}
int query(int x,int l,int r,int k) {
if(sumv[x]<k) return -;
if(l==r) return l;
int mid=l+r>>,k2=sumv[ls[x]];
if(k2>=k) return query(ls[x],l,mid,k);
return query(rs[x],mid+,r,k-k2);
}
struct Query {
int k,next,id;
}Q[maxn];
int ans[maxn],root[maxn],val[maxn];
void AddQuery(int k,int x,int id) {
Q[++cnt]=(Query){k,last[x],id};last[x]=cnt;
}
void dfs(int x,int fa) {
update(root[x],,,val[x]);
ren if(to[i]!=fa) {
dfs(to[i],x);
root[x]=merge(root[x],root[to[i]]);
}
for(int i=last[x];i;i=Q[i].next) ans[Q[i].id]=query(root[x],,,Q[i].k);
}
int main() {
n=read();q=read();
rep(i,,n) AddEdge(read(),read());
rep(i,,n) val[i]=read();
rep(i,,q) AddQuery(read(),read(),i);
dfs(,);
rep(i,,q) printf("%d\n",ans[i]);
return ;
}
之前的平衡树启发式合并。
#include<cstdio>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
const int maxn=;
struct Node
{
int r,s,v;
Node* ch[];
void maintain()
{
s=ch[]->s+ch[]->s+;
}
}*null=new Node(),nodes[maxn*];
int tot;
queue<Node*> Q;
Node* node()
{
if(!Q.empty())
{
Node* o=Q.front(); Q.pop();
return o;
}
return &nodes[tot++];
}
void del(Node* &o)
{
Q.push(o);
o=null;
}
void rotate(Node* &o,int d)
{
Node* k=o->ch[d^]; o->ch[d^]=k->ch[d]; k->ch[d]=o;
o->maintain(); k->maintain(); o=k;
}
void insert(Node* &o,int v)
{
if(o==null)
{
o=node();
o->ch[]=o->ch[]=null;
o->r=rand();
o->s=;
o->v=v;
}
else
{
int d=v>o->v;
insert(o->ch[d],v);
if(o->ch[d]->r>o->r) rotate(o,d^);
else o->maintain();
}
}
void remove(Node* &o,int v)
{
if(v==o->v)
{
if(o->ch[]!=null&&o->ch[]!=null)
{
int d=o->ch[]->r>o->ch[]->r;
rotate(o,d); remove(o->ch[d],v);
}
else
{
Node* k=o;
if(o->ch[]!=null) o=o->ch[];
else o=o->ch[];
del(k);
}
}
else remove(o->ch[v>o->v],v);
}
int query(Node* &o,int k)
{
if(k>o->s) return -;
if(k==o->ch[]->s+) return o->v;
if(k<=o->ch[]->s) return query(o->ch[],k);
return query(o->ch[],k-o->ch[]->s-);
}
void print(Node* &o)
{
if(o==null) return;
print(o->ch[]);
printf("%d ",o->v);
print(o->ch[]);
}
void merge(Node* &big,Node* &sm)
{
if(sm==null) return;
merge(big,sm->ch[]);
merge(big,sm->ch[]);
insert(big,sm->v);
del(sm);
}
Node* root[maxn];
int n,m;
int first[maxn],next[maxn*],to[maxn*];
void AddEdge(int a,int b)
{
to[++m]=b;
next[m]=first[a];
first[a]=m;
}
int First[maxn],Next[maxn],K[maxn],ans[maxn],Id[maxn];
void addquery(int x,int k,int id)
{
K[++m]=k;
Id[m]=id;
Next[m]=First[x];
First[x]=m;
}
void dfs(int x,int fa)
{
for(int i=first[x];i;i=next[i])
{
if(to[i]!=fa)
{
dfs(to[i],x);
if(root[x]->s<root[to[i]]->s) swap(root[x],root[to[i]]);
merge(root[x],root[to[i]]);
}
}
for(int i=First[x];i;i=Next[i]) ans[Id[i]]=query(root[x],K[i]);
}
int main()
{
int Q,a,b;
scanf("%d%d",&n,&Q);
for(int i=;i<n;i++)
{
scanf("%d%d",&a,&b);
AddEdge(a,b);
AddEdge(b,a);
}
for(int i=;i<=n;i++)
{
root[i]=node();
root[i]->s=;
root[i]->ch[]=root[i]->ch[]=null;
scanf("%d",&root[i]->v);
}
m=;
for(int i=;i<=Q;i++)
{
scanf("%d%d",&a,&b);
addquery(a,b,i);
}
dfs(,);
for(int i=;i<=Q;i++) printf("%d\n",ans[i]);
return ;
}
还有DFS序+主席树的version。
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
char ch=getchar();int sig=,x=;
while(!isdigit(ch)) {if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=x*+ch-'',ch=getchar();
return x*sig;
}
const int maxn=;
const int maxnode=;
int s[maxnode],ls[maxnode],rs[maxnode],ToT;
void update(int& y,int x,int l,int r,int pos)
{
s[y=++ToT]=s[x]+;if(l==r) return;
ls[y]=ls[x];rs[y]=rs[x];int mid=l+r>>;
if(pos<=mid) update(ls[y],ls[x],l,mid,pos);
else update(rs[y],rs[x],mid+,r,pos);
}
int query(int x,int y,int l,int r,int k)
{
if(l==r) return l;
int mid=l+r>>;
if(s[ls[y]]-s[ls[x]]>=k) return query(ls[x],ls[y],l,mid,k);
return query(rs[x],rs[y],mid+,r,k-s[ls[y]]+s[ls[x]]);
}
int to[maxn*],next[maxn*],first[maxn],e;
void AddEdge(int a,int b)
{
to[++e]=b;next[e]=first[a];first[a]=e;
to[++e]=a;next[e]=first[b];first[b]=e;
}
int L[maxn],R[maxn],v[maxn],root[maxn],pos[maxn],ts,siz[maxn];
void dfs(int x,int fa)
{
L[x]=++ts;pos[ts]=x;siz[x]=;
for(int i=first[x];i;i=next[i]) if(fa!=to[i]) dfs(to[i],x),siz[x]+=siz[to[i]];
R[x]=ts;
}
int main()
{
int n=read(),q=read(),x,k;
for(int i=;i<n;i++) AddEdge(read(),read());
for(int i=;i<=n;i++) v[i]=read();
dfs(,);
for(int i=;i<=n;i++) update(root[i],root[i-],,n,v[pos[i]]);
while(q--)
{
x=read();k=read();
if(siz[x]>=k) printf("%d\n",query(root[L[x]-],root[R[x]],,n,k));
else puts("-1");
}
return ;
}