#include <bits/stdc++.h>
using namespace std;
int n,joke[10009],temp;
vector <int> adj[10009];
bitset <102> dp[10001][101];
void dfs(int node) {
dp[node][joke[node]][joke[node]] = 1;
temp = joke[node];
sort(adj[node].begin(),adj[node].end(),[] (int a,int b) {
return abs(joke[a] - temp) < abs(joke[b] - temp);
});
for (auto child : adj[node]) {
dfs(child);
//TH1: [x][node] (joke[x] < joke[node])
if (joke[child] < joke[node]) {
for (int left = 1;left <= joke[child];left++) {
for (int right = joke[child];right < joke[node];right++) if (dp[child][left][right]) {
dp[node][left] |= dp[node][right + 1];
}
}
}
//TH2: [node][x] (joke[node] < joke[x])
if (joke[node] < joke[child]) {
for (int left = joke[node];left >= 1;left--) {
for (int right = joke[node];right <= 100;right++) if (dp[node][left][right]) {
dp[node][left] |= dp[child][right + 1];
}
}
}
}
// cout << "node: " << node << '\n';
// for (int i = 1;i <= 6;i++) {
// for (int j = 1;j <= 6;j++) {
// cout << "[" << i << "," << j << "]" << ":" << dp[node][i][j] << '\n';
// }
// }
}
int main() {
ios_base::sync_with_stdio(0);cin.tie(nullptr);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin >> n;
for (int i = 1;i <= n;i++) cin >> joke[i];
for (int i = 1;i < n;i++) {
int u,v;cin >> u >> v;
adj[u].push_back(v);
}
dfs(1);
int res = 0;
for (int i = 1;i <= 100;i++) res += dp[1][i].count();
cout << res;
}
/*
Nho doi vai em gay
co gai ay ngoi duoi goc pho nen tho ...
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |