Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- class Solution {
- public:
- vector<int> solve(int n, vector<vector<int>>& g, int q, vector<vector<int>>& queries) {
- vector<vector<int>> adj(n + 1);
- for (int i = 0; i < g.size(); ++i) {
- int u = g[i][0], v = g[i][1];
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- vector<int> ans;
- for (int i = 0; i < queries.size(); ++i) {
- int x = queries[i][0];
- int k = queries[i][1];
- vector<int> parent(n + 1, -1);
- vector<int> size_vec(n + 1, 1);
- stack<pair<int, bool>> postack;
- postack.push(make_pair(x, false));
- while (!postack.empty()) {
- pair<int, bool> top = postack.top();
- int u = top.first;
- bool processed = top.second;
- postack.pop();
- if (!processed) {
- postack.push(make_pair(u, true));
- vector<int> children;
- for (int j = 0; j < adj[u].size(); ++j) {
- int v = adj[u][j];
- if (v != parent[u]) {
- children.push_back(v);
- }
- }
- reverse(children.begin(), children.end());
- for (int j = 0; j < children.size(); ++j) {
- int v = children[j];
- parent[v] = u;
- postack.push(make_pair(v, false));
- }
- } else {
- for (int j = 0; j < adj[u].size(); ++j) {
- int v = adj[u][j];
- if (v != parent[u]) {
- size_vec[u] += size_vec[v];
- }
- }
- }
- }
- vector<int> all_sizes;
- for (int j = 1; j <= n; ++j) {
- all_sizes.push_back(size_vec[j]);
- }
- sort(all_sizes.begin(), all_sizes.end());
- if (k - 1 < all_sizes.size()) {
- ans.push_back(all_sizes[k - 1]);
- } else {
- ans.push_back(-1);
- }
- }
- return ans;
- }
- };
- int main()
- {
- int n;cin >> n;
- vector<vector<int>>adj(n-1,vector<int>(2,0));
- for(int i = 0; i < n - 1; i++)
- {
- cin >> adj[i][0] >> adj[i][1];
- }
- int q;cin >> q;
- vector<vector<int>>queries(q,vector<int>(2,0));
- for(int i = 0; i < q; i++)
- cin>>queries[i][0]>>queries[i][1];
- Solution sol;
- vector<int>ans = sol.solve(n,adj,q,queries);
- for(int i = 0; i < ans.size();i++)
- cout << ans[i] << " ";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
