题目描述
现在有一颗n个结点且根结点为1的树,第i条边连接$A_i$与$B_i$
树上的每个节点的权值为w[i]
现在有Q个问题,每个问题给出一个$V_i$与$K_i$,算出以$V_i$为根结点的子树中,第$K_i$大的权值
输入样例
5 2
1 2 3 4 5
1 4
2 1
2 5
3 2
1 2
2
输出样例
4
5
算法 (dfs)
首先我们看一下题目所给出的数据范围,K的大小小于等于20,那样其实我们可以将所有点的子树的权值从大到小排序(如果多于20个我们就只选择20个)然后直接查表写出结果就可以啦
dfs思路
1.将自己的权值存下来
2.处理子树
3.排序取前20个(小于20个全部存下来)
void dfs(int u,int fa)
{
vector<int> v;
v.push_back(w[u]);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u);
for(auto t:ans[j]) v.push_back(t);
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
int cnt=min(20,(int)v.size());
for(int i=0;i<cnt;i++) ans[u].push_back(v[i]);
}
c++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>
#include<vector>
#include<map>
#include<set>
#include<queue>
using namespace std;
const int N=1e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int w[N];
int n,q;
vector<int> ans[N];
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void dfs(int u,int fa)
{
vector<int> v;
v.push_back(w[u]);
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dfs(j,u);
for(auto t:ans[j]) v.push_back(t);
}
sort(v.begin(),v.end());
reverse(v.begin(),v.end());
int cnt=min(20,(int)v.size());
for(int i=0;i<cnt;i++) ans[u].push_back(v[i]);
}
int main()
{
cin>>n>>q;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d %d",&x,&y);
add(x,y);
add(y,x);
}
dfs(1,-1);
while(q--)
{
int x,k;
scanf("%d %d",&x,&k);
k--;
printf("%d\n",ans[x][k]);
}
}