Omówienie zadania Tree Queries (Codeforces) – DFS / PreOrder / PostOrder

Omówienie zadania Tree Queries (Codeforces) – DFS / PreOrder / PostOrder

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;
}
Link do pliku ze wzorcowym kodem C++ zadania Tree Queries 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz