Untitled

mail@pastecode.io avatar
unknown
c_cpp
a month ago
1.3 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> adj_list;
vector<vector<int>> sub_weight;
vector<int> weight;
vector<bool> visited;

void dfs(int u, vector<vector<int>> &adj, vector<bool> &vis)
{
    vis[u] = true;
    sub_weight[u].emplace_back(weight[u]);
    for (auto v : adj_list[u])
    {
        if (!vis[v])
        {
            dfs(v, adj, vis);
            sub_weight[u].insert(sub_weight[u].end(), sub_weight[v].begin(), sub_weight[v].end());
        }
    }
    sort(sub_weight[u].begin(), sub_weight[u].end(), greater<int>());
    if (sub_weight[u].size() > 20)
        sub_weight[u].resize(20);
}

int main()
{
    ios::sync_with_stdio(), cin.tie(0), cout.tie(0);

    int n, q;
    cin >> n >> q;

    adj_list.resize(n + 5);
    weight.resize(n + 5);
    sub_weight.resize(n + 5);
    visited.resize(n + 5, false);
    for (int i = 1; i <= n; ++i)
    {
        cin >> weight[i];
    }
    for (int i = 0; i < n - 1; ++i)
    {
        int a, b;
        cin >> a >> b;
        adj_list[a].emplace_back(b);
        adj_list[b].emplace_back(a);
    }

    dfs(1, adj_list, visited);

    for (int i = 0; i < q; ++i)
    {
        int v, k;
        cin >> v >> k;
        cout << sub_weight[v][k - 1] << "\n";
    }
}
Leave a Comment