abc239_e Subtree K-th Max（dfs，贪心优化）

原题链接

题目大意

$n$ 个数，$q$ 个询问
接下来一行 $n$ 个数：$x_i$ 表示第 $i$ 个点的权值是 $x_i$
接下来 $n?1$ 行，每行两个数 $a,b$，表示 $a$ 和 $b$ 之间有一条边
接下来 $q$ 行，每行两个数 $a,b$ ，问以 $a$ 为根节点的子树中所有节点权值的第 $b$ 大是多少。

$2\le N\le 10^5$

$0\le X_i\le 10^9$

$1\le A_i,B_i\le N$

$1\le Q\le 10^5$

$1\le V_i\le N$

$1\le K_i\le 20$

思路

结合代码看。
开一个二维数组，$ans[i][j]$ 代表以 $i$ 为根节点的子树，第 $j$ 大的权值是几，
然后就是每次搜到最后一层回溯时，把当前 $order$ 里的所有点权排个序，然后只取最大的前 $20$ 个，如果不足 $20$ 则全都取，存进 $ans$ 数组，然后回溯后，再把当前这个节点 $ans$ 数组里所有的点权全都存进当前u节点的 $order$ 里面，然后知道遍历完当前 $u$ 节点，再重复之前的操作。

之所以可以直接取前 $20$ 是因为，当前节点的另一颗子树里的点权有多大或多小，对于当前节点来说，想去最大值也仅仅是和前一个子树的前 $20$ 大比，不在前 $20$ 大里的也没有比较的意义，所以可以直接取所有的前0大来比较。

然后输出时注意第 $j$ 大要 $?1$，因为数组从 $0$ 开始。

代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 1e5 + 10;vector<int> g[N], ans[N], X(N);int n, q;void dfs(int u, int fa)
{
    vector<int> order;order.push_back(X[u]);//放进它本身for (int i = 0; i < (int)g[u].size(); i ++ ){
    int j = g[u][i];if (j == fa) continue;dfs(j, u);for (int k = 0; k < (int)ans[j].size(); k ++ ){
    int v = ans[j][k];order.push_back(v); //存的是值 }}sort(order.begin(), order.end(), greater<int>());int num = min(20, (int)order.size());for (int i = 0; i < num; i ++ ){
    ans[u].push_back(order[i]); //order里面是值 }return;
}int main()
{
    cin >> n >> q;for (int i = 1; i <= n; i ++ ){
    cin >> X[i];}for (int i = 1; i < n; i ++ ){
    int a, b; cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}dfs(1, -1);
// for (int i = 1; i <= n; i ++ )
// {
    
// for (auto j : ans[i]) cout << j << " ";
// cout << endl;
// }while (q -- ){
    int a, b;cin >> a >> b;cout << ans[a][b - 1] << endl;}return 0;
}

总结

比赛结束后背了个单词，花了一个多小时重新做了一遍前五题，虽然第五题也借鉴了别人的代码，但也算是弄懂了。

这次比赛的情况十分不理想，复盘完，心中颇有些一雪前耻的感觉。

总结一下，就是感觉最近状态十分不好，只要往电脑前一坐就开始头晕，感觉不能思考，应该是最近作息越来越不正差所导致的。还有就是我自己十分不会管理时间，导致任务完不成，最后人挺累的，但却啥都没干好。

以后无论干什么事的时候都要想一下，我是为了什么而开始干这件事，明确目标后抓紧时间……