Szczegółowe omówienie zadania E. Tree Queries z platformy Codeforces (grafy / DFS / PreOrder / PostOrder):
Link do powyższego omówienia zadania E. Tree Queries:
https://youtu.be/weANP6rubWA
–
Link do treści zadania E. Tree Queries:
https://codeforces.com/problemset/problem/1328/E
–
Zadanie E. Tree Queries to zadanie grafowe i wymaga użycia techniki PreOrder / PostOrder.
Te wartości uzyskujemy stosując algorytm DFS.
–
Zadanie pochodzi z platformy Codeforces – jednej z najpopularniejszych platform algorytmicznych.
Jak się uczyć na podstawie takiego zadania?
https://tiny.pl/7x1gg
Zadanie omawia Mikołaj Bulge.
——-
Kod C++ programu Tree Queries, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include<bits/stdc++.h>
using namespace std;
constexpr int M=2e5+7;
vector<int>g[M];
vector<int>vctr;
int parent[M];
int depth[M];
pair<int,int>prepost[M];
bool was[M];
int tajm=0;
void dfs(int v){
prepost[v].first=++tajm;
for(auto w:g[v]){
if(w==parent[v]) continue;
parent[w]=v;
depth[w]=depth[v]+1;
dfs(w);
}
prepost[v].second=++tajm;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
bool ok;
int n,q,k,a,b,v;
cin>>n>>q;
for(int i=1; i<n; i++){
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
dfs(1);
while(q--){
ok=1; v=1;
cin>>k;
while(k--){
cin>>a;
if(a>1) a=parent[a];
if(depth[a]>depth[v]) v=a;
vctr.push_back(a);
}
for(auto w:vctr){
if(w==v) continue;
if(!(prepost[w].first<prepost[v].first&&prepost[w].second>prepost[v].second)) ok=0;
}
vctr.clear();
cout << (ok ? "YES\n" : "NO\n");
}
return 0;
}