Cod sursa(job #2771321)

Utilizator nubnubMeh Neh nubnub Data 26 august 2021 15:59:32
Problema Medie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream in("maimute.in");
ofstream out("maimute.out");

struct inter{
	int beg, end;
};

const int nmax = 100006;
int n, m, act = 1;
vector<int> vecini[nmax];
bool viz[nmax];
inter v[nmax];

void dfs(int x)
{
	viz[x] = 1;
	v[x].beg = act;

	for(int i = 0; i<(int)vecini[x].size(); i++)
	{
		if(viz[vecini[x][i]]==0)
		{
			act++;
			dfs(vecini[x][i]);
		}
	}

	v[x].end = act;
}

int main(){
	int player_unu=0;

	in>>n;
	for(int i = 1; i<n; i++)
	{
		int x, y;
		in>>x>>y;
		vecini[x].push_back(y);
		vecini[y].push_back(x);
	}

	dfs(1);

	in>>m;
	for(int i = 0; i<m; i++)
	{
		int x, y;
		in>>x>>y;
		if((v[x].beg<=v[y].beg && v[x].end>=v[y].end) || (v[y].beg<=v[x].beg && v[y].end>=v[x].end))
			out<<"DA\n";
		else
			out<<"NU\n";
	}

	return player_unu;
}