G
meda
c_cpp
9 months ago
1.8 kB
20
Indexable
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
void SOLVE() {
int n, k, q; cin >> n >> k >> q;
vector<bool> good(n + 1);
vector<vector<int>> graph(n + 1);
for(int i = 0, x; i < k; i++){
cin >> x;
good[x] = true;
}
for(int i = 0, u, v; i < n - 1; i++){
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
vector<int> dp(n + 1), dp2(n + 1);
function<int(int, int)> dfs =[&] (int node, int parent){
for(auto child : graph[node]){
if(child == parent) continue;
dp[node] = max(dp[node], dfs(child, node));
}
return dp[node] = dp[node] + good[node];
};
function<void(int, int)> dfs2 =[&] (int node, int parent){
multiset<int> ms;
for(auto child : graph[node]){
if(child == parent) continue;
ms.insert(dp[child]);
}
for(auto child : graph[node]){
if(child == parent) continue;
dp2[child] = dp2[node] + good[child];
ms.erase(ms.find(dp[child]));
if(ms.size())
dp2[child] = max(dp2[child], good[child] + good[node] + *ms.rbegin());
ms.insert(dp[child]);
dfs2(child, node);
}
};
dfs(1, -1);
dp2[1] = good[1];
dfs2(1, -1);
int X = max(*max_element(dp.begin(), dp.end()), *max_element(dp2.begin(), dp2.end()));
while(q--){
int u; cin >> u;
cout << (max(dp[u], dp2[u]) == X ? "JA" : "NEIN") << endl;
}
}
signed main(){
ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr);
int o_o; cin >> o_o; while(o_o--)
SOLVE(); return 0;
}Editor is loading...
Leave a Comment