Submission #1179376

#TimeUsernameProblemLanguageResultExecution timeMemory
1179376RandomUserUzastopni (COCI15_uzastopni)C++20
160 / 160
287 ms17904 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e4 + 5; int n, a[N], ans = 0; vector<int> G[N]; bitset<100> dp[N][101]; void dfs(int u, int p) { a[u]--; dp[u][a[u]][a[u]] = 1; for(int v : G[u]) { if(v == p) continue; dfs(v, u); for(int i=0; i<100; i++) for(int j=i; j<100; j++) if(!(i <= a[u] && a[u] <= j) && dp[v][i][j]) dp[u][i][j] = 1; } for(int i=99; i>=0; i--) for(int j=i; j<100; j++) if(dp[u][i][j]) dp[u][i] |= dp[u][j+1]; for(int i=0; i<100; i++) for(int j=i; j<100; j++) if(j < a[u] || a[u] < i) dp[u][i][j] = 0; } int main() { cin >> n; for(int i=1; i<=n; i++) cin >> a[i]; for(int i=1; i<n; i++) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } dfs(1, 1); for(int i=0; i<100; i++) for(int j=i; j<100; j++) ans += dp[1][i][j]; cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...