제출 #98697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98697		Dat160601	Uzastopni (COCI15_uzastopni)	C++17	160 / 160	20 ms	3552 KiB

uzastopni

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N = 1e4 + 7;

int n, u, v, a[N];
bool vis[2][N], l[101][N], r[101][N];
long long ans = 0, bns = 0;
vector <int> edge[N];

void dfs(int u){
	for(int v : edge[u]) dfs(v);
	l[a[u]][u] = r[a[u]][u] = 1;
	for(int i = a[u]; i > 1; i--){
		if(!l[i][u]) continue;
		for(int v : edge[u]){
			if(vis[0][v] || !r[i - 1][v]) continue;
			vis[0][v] = true;
			for(int j = 1; j <= 100; j++) l[j][u] = max(l[j][u], l[j][v]);
		}
	}
	for(int i = a[u]; i < 100; i++){
		if(!r[i][u]) continue;
		for(int v : edge[u]){
			if(vis[1][v] || !l[i + 1][v]) continue;
			vis[1][v] = true;
			for(int j = 1; j <= 100; j++) r[j][u] = max(r[j][u], r[j][v]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		edge[u].pb(v);
	}
	dfs(1);
	for(int i = 1; i <= 100; i++) ans += l[i][1];
	for(int i = 1; i <= 100; i++) bns += r[i][1];
	cout << ans * bns;
}

• Subtask 1: 160 / 160