您的位置:首页 > 游戏 > 游戏 > 黄骅百度贴吧招聘_公司网站制作合同_西安seo外包优化_windows优化大师下载

黄骅百度贴吧招聘_公司网站制作合同_西安seo外包优化_windows优化大师下载

2024/12/7 14:04:30 来源:https://blog.csdn.net/2301_80882026/article/details/143643532  浏览:    关键词:黄骅百度贴吧招聘_公司网站制作合同_西安seo外包优化_windows优化大师下载
黄骅百度贴吧招聘_公司网站制作合同_西安seo外包优化_windows优化大师下载

[ABC239E] Subtree K-th Max

题面翻译

给定一棵 n n n 个节点的树,每个节点的权值为 x i x_i xi

现有 Q Q Q 个询问,每个询问给定 v , k v,k v,k,求节点 v v v 的子树第 k k k 大的数。

0 ≤ x i ≤ 1 0 9 , 2 ≤ n ≤ 1 0 5 , 1 ≤ Q ≤ 1 0 5 , 1 ≤ k ≤ 20 0\le x_i\le10^9,2\le n\le10^5,1\le Q\le10^5,1\le k\le20 0xi109,2n105,1Q105,1k20

翻译提供:xiaohaoaibiancheng66

题目描述

$ N $ 頂点の根付き木があります。頂点には $ 1 $ から $ N $ の番号がついており、根は頂点 $ 1 $ です。
$ i $ 番目の辺は頂点 $ A_i $ と $ B_i $ を結んでいます。
頂点 $ i $ には整数 $ X_i $ が書かれています。

$ Q $ 個のクエリが与えられます。$ i $ 番目のクエリでは整数の組 $ (V_i,K_i) $ が与えられるので、次の問題に答えてください。

  • 問題:頂点 $ V_i $ の部分木に含まれる頂点に書かれた整数のうち、大きい方から $ K_i $ 番目の値を求めよ

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ Q $ $ X_1 $ $ \ldots $ $ X_N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ V_1 $ $ K_1 $ $ \vdots $ $ V_Q $ $ K_Q $

输出格式

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

样例 #1

样例输入 #1

5 2
1 2 3 4 5
1 4
2 1
2 5
3 2
1 2
2 1

样例输出 #1

4
5

样例 #2

样例输入 #2

6 2
10 10 10 9 8 8
1 4
2 1
2 5
3 2
6 4
1 4
2 2

样例输出 #2

9
10

样例 #3

样例输入 #3

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

样例输出 #3

1
10
100
1000

提示

制約

  • $ 2\ \leq\ N\ \leq\ 10^5 $
  • $ 0\leq\ X_i\leq\ 10^9 $
  • $ 1\leq\ A_i,B_i\leq\ N $
  • $ 1\leq\ Q\ \leq\ 10^5 $
  • $ 1\leq\ V_i\leq\ N $
  • $ 1\leq\ K_i\leq\ 20 $
  • 与えられるグラフは木である
  • 頂点 $ V_i $ の部分木は頂点を $ K_i $ 個以上持つ
  • 入力に含まれる値は全て整数である

Sample Explanation 1

この入力において与えられる木は下図のようなものです。 ![図](https://img.atcoder.jp/ghi/e2bc1237d64f79f33181e6f54c9f7ce7.png) $ 1 $ 番目のクエリでは、頂点 $ 1 $ の部分木に含まれる頂点 $ 1,2,3,4,5 $ に書かれた数のうち大きい方から $ 2 $ 番目である $ 4 $ を出力します。 $ 2 $ 番目のクエリでは、頂点 $ 2 $ の部分木に含まれる頂点 $ 2,3,5 $ に書かれた数のうち大きい方から $ 1 $ 番目である $ 5 $ を出力します。

思路:刚看到这种题,就感觉写起来很别扭怎么,还是要敢写才行,错了不要紧,根据k的范围我们可以知道我们只需要暴力遍历即可得出来每一个节点前20大的数

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e5 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e6 + 10;vector<ll>ans[N], a(N + 1), ed[N];//存树void dfs(int u, int fa)
{vector<ll>o;o.push_back(a[u]);//存上自己for(auto it : ed[u]){if(it == fa) continue;dfs(it, u);//一直遍历it那一个节点for(auto k : ans[it])//相当于那个节点上的数都给遍历完了{o.push_back(k);}}sort(o.begin(), o.end(), greater<ll>());//排好序//我们只需要取出前20即可int si = min(20, (int)o.size());for(int i = 0; i < si; i ++){ans[u].push_back(o[i]);}
}
int main()
{int n, q;cin >> n >> q;for(int i = 1; i <= n; i ++){cin >> a[i];}for(int i = 1; i <= n - 1; i ++){int u, v;cin >> u >> v;ed[u].push_back(v);ed[v].push_back(u);//存图}dfs(1, -1);//预处理出来第k大while(q --){int u, k;cin >> u >> k;cout << ans[u][k - 1] << endl;//因为下标从0开始的}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com