Untitled
unknown
plain_text
a year ago
2.0 kB
9
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