Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define DEBUG true
- #define ll int
- #define tki(x) int x;scanf("%d",&x);
- #define tkll(x) ll x;scanf("%ll",&x);
- #define vll vector<ll>
- #define vii vector<int>
- #define PB push_back
- #define EB emplace_back
- #define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
- #define forll(i,j,k) for(ll i=j;i<k;i++)
- #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
- #define all(x) (x).begin(), (x).end()
- #define endl "\n"
- class Node{
- public:
- int height;
- int parent;
- vector<int> child;
- };
- // vector<Node *> T;/
- void dfs(vector<Node *> &T,ll a){
- for(auto x : T[a]->child){
- T[x]->height = (T[a]->height) + 1;
- dfs(T,x);
- }
- }
- int main(){
- FASTIO
- tki(N);tki(M);
- int *height = new int[N];
- int *parent = new int[N];
- {
- vector<Node *> T(N);
- rep(i,0,N){T[i] = new Node;}
- T[0]->height = 1;
- T[0]->parent = 0;
- rep(i,0,N-1){
- tki(a);tki(b);
- (T[min(a-1,b-1)]->child).EB(max(a-1,b-1));
- T[max(a-1,b-1)]->parent = min(a-1,b-1);
- }
- dfs(T,0);
- forll(i,0,N){height[i] = T[i]->height;parent[i] = T[i]->parent;}
- }
- // delete &T;
- int K;
- int maxi = 0;
- int lastNode = 0;
- vector<int> v;
- vector<int> path;
- forll(i,0,M){
- scanf("%d",&K);
- v.resize(K);
- for(int i=0;i<K;i++){
- scanf("%d",&v[i]);
- v[i]--;
- }
- if(K >= 2){
- maxi = 0;
- lastNode = 0;
- forll(j,0,K){
- if(height[v[j]] > maxi){maxi= height[v[j]];lastNode = v[j];}
- }
- path.resize(maxi);
- path[maxi-1] = lastNode;
- for(ll j = maxi-2;j>=0;j--){
- path[j] = parent[path[j+1]];
- }
- bool f = true;
- forll(j,0,K){
- if(height[v[j]] >= 2){
- if(parent[v[j]] != path[height[v[j]] - 2]){f=false;break;}
- }
- }
- if(f){printf("YES\n");}
- else{
- printf("NO\n");
- }
- }
- else{
- printf("YES\n");
- }
- }
- }
Add Comment
Please, Sign In to add comment