Untitled

 avatar
unknown
plain_text
a year ago
2.0 kB
5
Indexable
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#ifdef ONLINE_JUDGE
#define debug(x...)
#define testcase(tc)
#else
#include "debug.h"
#endif

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;

#define int long long int
#define tp3(T) tuple<T,T,T>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pr(x) cout << x << endl
#define yesno(x) cout << ((x) ? "YES\n" : "NO\n")
#define sz(x) (int)x.size()
const int N = 200100;
int curr;
void dfs(int node, vector<vector<int>> &adj, vector<int> &vis2, vector<int> &vis1){
  vis2[node] = 1;
  curr = node;
  // debug(vis2);
  for(auto x : adj[node]){
    // debug(x,vis2[x], vis1[x]);
    if(!vis2[x] && !vis1[x]){
      dfs(x, adj, vis2, vis1);
    }
  }
}
void dxt(){
  int n,m;
  cin >> n >> m;
  
  vector<vector<int>> adj(n + 1);
  for(int i = 1; i < n; i++){
    int a,b; cin >> a >> b;
    if(a < b) swap(a,b);
    adj[a].push_back(b);
  }
  
  vector<int> pos(m + 1);
  for(int i = 1; i <= m; ++i) cin >> pos[i];
  // debug(pos);
  vector<int> vis1(n + 1, 0), ans(n + 1), vis2(n + 1,0);
  for(int i = 1; i <= m; ++i){
    fill(all(vis2), 0LL);
    curr = 0;
    dfs(pos[i], adj, vis2, vis1);
    if(curr == 0|| vis1[curr])
      ans[i] = -1;
    else
      ans[i] = curr, vis1[curr] = 1;
    // debug(vis1);
      
  }
  for(int i = 1; i <= m; i++){
    cout << ans[i] << " ";
  }
  cout << endl;
}

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int test_cases = 1;
  cin >> test_cases;
  for(int i = 1; i <= test_cases; i++){
    dxt();
  }
  return 0;
}
Editor is loading...
Leave a Comment