#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
const int mx = 10005, mv = 12;
int n, A[mx], ans; vector<int> adj[mx]; bitset<mv> dp[mx][mv];
void dfs(int i){
dp[i][A[i]][A[i]] = 1;
for (int x : adj[i]){
dfs(x);
FOR(j, 0, mv){
if (j < A[i]) dp[i][j] |= dp[x][j] << (mv - A[i]) >> (mv - A[i]);
if (j > A[i]) dp[i][j] |= dp[x][j];
}
}
for (int j = mv - 1; j; j--) FOR(k, j, mv - 1)
if (dp[i][j][k]) dp[i][j] |= dp[i][k + 1];
FOR(j, 0, mv){
if (j <= A[i]) dp[i][j] = dp[i][j] >> A[i] << A[i];
else dp[i][j].reset();
}
}
int main(){
cin >> n;
FOR(i, 0, n) cin >> A[i];
FOR(i, 0, n - 1){
int a, b; cin >> a >> b;
adj[a - 1].push_back(b - 1);
}
dfs(0);
FOR(i, 0, mv) ans += dp[0][i].count();
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
536 KB |
Output is correct |
| 2 |
Correct |
1 ms |
460 KB |
Output is correct |
| 3 |
Correct |
1 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1 ms |
460 KB |
Output is correct |
| 5 |
Correct |
1 ms |
460 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
540 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 11 |
Incorrect |
11 ms |
1740 KB |
Output isn't correct |
| 12 |
Correct |
11 ms |
1744 KB |
Output is correct |
| 13 |
Correct |
12 ms |
1692 KB |
Output is correct |
| 14 |
Incorrect |
11 ms |
2656 KB |
Output isn't correct |
| 15 |
Incorrect |
11 ms |
2636 KB |
Output isn't correct |
| 16 |
Incorrect |
11 ms |
2636 KB |
Output isn't correct |
| 17 |
Correct |
11 ms |
1740 KB |
Output is correct |
| 18 |
Correct |
11 ms |
1684 KB |
Output is correct |
| 19 |
Runtime error |
11 ms |
3004 KB |
Execution killed with signal 11 |
| 20 |
Execution timed out |
1082 ms |
1912 KB |
Time limit exceeded |
