Cod sursa(job #2607092)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 29 aprilie 2020 11:07:24
Problema Guvern Scor 0
Compilator cpp-64 Status done
Runda why Marime 2.1 kb
#include <cstring>
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
const int SIZE = 200002;
 
typedef vector<int> VI;
typedef vector<pair<int, int> > VP;
 
int N, result;
VI V[SIZE], Term[SIZE];
VP aux;
int val[SIZE], P[SIZE], pos[SIZE], pose[SIZE], where[SIZE], pnow;
int D[SIZE];
bool S[SIZE];
 
class set_compare
{
	public:
		bool operator () (const int& i1, const int& i2)
		{
			return i1 < i2;
		}
};
set<int, set_compare> Set;
 
inline int compare(const int& i1, const int& i2)
{
	return val[i1] < val[i2];
}
 
void compM(int x)
{
	S[x] = true;
	pos[x] = ++pnow;
	
	set<int, set_compare>::iterator Aval = Set.lower_bound(val[x]);
	int value = P[(Aval == Set.end() ? 0 : *Aval)];
	where[x] = value;
	
	if (value != 0) Term[value].push_back(x);
	
	Set.insert(val[x]);
	
	for (VI::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!S[*it])
			compM(*it);
	
	Set.erase(Set.find(val[x]));
	pose[x] = ++pnow;
}
void Dfs(int x)
{
	S[x] = true;
	for (VI::iterator it = V[x].begin(); it != V[x].end(); ++it)
		if (!S[*it])
			Dfs(*it);
	
	for (VI::iterator it = Term[x].begin(); it != Term[x].end(); ++it)
	{
		aux.push_back(make_pair(*it, D[*it]));
		if (aux.size() >= 2 && pos[aux[aux.size() - 1].first] >= pos[aux[aux.size() - 2].first] && pose[aux[aux.size() - 1].first] <= pose[aux[aux.size() - 2].first])
		{
			aux[aux.size() - 2].second = max(aux[aux.size() - 2].second, aux[aux.size() - 1].second);
			aux.pop_back();
		}
	}
	
	D[x] = 1;
	for (VP::iterator it = aux.begin(); it != aux.end(); ++it)
		D[x] += it->second;
	aux.clear();
}
 
int main()
{
	ifstream fin("guvern.in");
	ofstream fout("guvern.out");
	
	fin >> N;
	for (int i = 1, nod1, nod2; i < N; ++i)
	{
		fin >> nod1 >> nod2;
		V[nod1].push_back(nod2);
		V[nod2].push_back(nod1);
	}
	for (int i = 1; i <= N; ++i)
	{
		fin >> val[i];
		P[i] = i;
	}
	
	sort(P + 1, P + N + 1, compare);
	for (int i = 1; i <= N; ++i)
		val[P[i]] = i;
	compM(1);
	
	memset(S, 0, sizeof(S));
	Dfs(1);
	
	for (int i = 1; i <= N; ++i)
		result = max(result, D[i]);
	fout << result;
	
	fin.close();
	fout.close();
}