Submission #1721383

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[3001];
vi adj[3001];
bool dp[3001];

void dfs(int u, int p)
{
	dp[u] = 0;
	ll sum = 0;
	bool leaf=1;
	bool exp1 = 0;
	ll mini = -1;
	for(int i = 0; i < adj[u].size(); i++)
	{
		int v = adj[u][i];
		if(v==p) continue;
		dfs(v,u);
		if(!dp[v]&&a[v]<a[u]) 
		{
			exp1=1;
		}
		leaf=0;
	}
	//cerr<<u<<' '<<sum<<' '<<mini<<' '<<'\n';
	
	if(leaf) 
	{
		dp[u]=0;
		return ;
	}
	if(!exp1) return ;
	dp[u]=1;
	//cerr<<u<<' '<<dp[u]<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
	}
	for(int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin>>u>>v;
		u--; v--;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	vi vec;
	for(int i = 0; i < n; i++)
	{
		dfs(i,-1);
		if(dp[i]) vec.pb(i);
	}
	for(int i = 0; i < vec.size(); i++)
	{
		cout<<vec[i]+1;
		if(i+1<vec.size()) cout<<' ';
	}
	cout<<'\n';
}

Submission Info

Judge Result