题意：
一棵树，每次查询某个子树的第k大
思路：
询问子树的问题，因为子树的dfs序是连续的一个区间，所以我们将这棵树dfs地建立主席树，查询子树就是查询子树对应的区间，这样就把树变成数列了
错误及反思：
其实很简单，但是spoj卡常啊，在优化了常数，vector变成链式前向星，用了快读，换头文件以后终于ac了
代码：
#include<map>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define lson l,m
#define rson m+1,r
const int N = 101000;
int sum[N*20],ls[N*20],rs[N*20],val[N],root[N],fa[N],to[N],rnk[N],id[N],first[N];
int n,q,tot=1,cnt=0,tid=0;
vector<int> v;
map<int,int> mp;struct EDGE{int to,next;
}e[N*2];inline int read() {char ch = getchar(); int x = 0, f = 1;while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch = getchar();} while('0' <= ch && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();} return x * f;
}void addedge(int x,int y){e[tid].to=y;e[tid].next=first[x];first[x]=tid++;e[tid].to=x;e[tid].next=first[y];first[y]=tid++;
}int getid(int x){
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}int build(int l,int r){int rt=++cnt;ls[rt]=rt; rs[rt]=rt; sum[rt]=0;if(l==r) return rt;int m=l+r>>1;ls[rt]=build(lson);rs[rt]=build(rson);return rt;
}int update(int pre,int pos,int l,int r){int rt=++cnt;ls[rt]=ls[pre]; rs[rt]=rs[pre]; sum[rt]=sum[pre]+1;if(l==r) return rt;int m=l+r>>1;if(m>=pos) ls[rt]=update(ls[pre],pos,lson);else rs[rt]=update(rs[pre],pos,rson);return rt;
}void dfs(int now,int Fa){root[tot]=update(root[tot-1],getid(val[now]),1,v.size());id[now]=tot;fa[now]=Fa; tot++;for(int i=first[now];i!=-1;i=e[i].next)if(e[i].to!=Fa)dfs(e[i].to,now);to[now]=tot-1;
}int query(int r1,int r2,int k,int l,int r){if(l==r) return rnk[l-1];int m=l+r>>1,num=sum[ls[r2]]-sum[ls[r1]];if(num>=k) return query(ls[r1],ls[r2],k,lson);return query(rs[r1],rs[r2],k-num,rson);
}int main(){memset(first,-1,sizeof(first));n=read();for(int i=1;i<=n;i++){ val[i]=read(); mp[val[i]]=i; v.push_back(val[i]);}sort(v.begin(),v.end());for(int i=0;i<v.size();i++){rnk[i]=mp[v[i]];}for(int i=1,u,v;i<n;i++){u=read(); v=read();addedge(u,v);}root[0]=build(1,v.size());dfs(1,0);scanf("%d",&q);while(q--){int x,k;scanf("%d%d",&x,&k);printf("%d\n",query(root[id[x]-1],root[to[x]],k,1,v.size()));}
}