G

 avatar
meda
c_cpp
10 months ago
1.8 kB
21
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