#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "uzastopni"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 1e4 + 9;
int n, a[MAXN];
vector<int> g[MAXN];
ii edge[MAXN];
namespace subtask1{
bool checkSubtask1(){
return n <= 100;
}
int sz[102], mx;
bool dp[102][102][102];
bool reachable[102][102][102];
void dfs(int u, int p){
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
dfs(v, u);
for(int j = 1; j <= mx; j++){
for(int k = j; k <= mx; k++){
if (dp[v][j][k] and j <= a[v] and a[v] <= k) {
reachable[u][j][k] = true;
}
}
}
}
// if (u == 1){
// for(int l = 1; l <= mx; l++){
// for(int r = l; r <= mx; r++){
// if (reachable[u][l][r]) cout << u << ' ' << l << ' ' << r << endl;
// }
// }
// }
for(int i = mx; i >= 1; i--){
if (i == a[u]){
dp[u][a[u]][a[u]] = true;
for(int j = i + 1; j <= mx; j++){
if (dp[u][a[u] + 1][j]) dp[u][i][j] = true;
}
}
if (i > a[u]){
for(int j = i; j <= mx; j++){
if (reachable[u][i][j]) {
dp[u][i][j] = true;
for(int k = j + 1; k <= mx; k++){
if (dp[u][j + 1][k]) {
dp[u][i][k] = true;
}
}
}
}
}
if (i < a[u]){
for(int j = i; j < a[u]; j++){
if (reachable[u][i][j]){
for(int k = j + 1; k <= mx; k++){
if (dp[u][j + 1][k]) dp[u][i][k] = true;
}
}
}
}
}
}
void solveSubtask1(){
memset(dp, false, sizeof(dp));
memset(reachable, false, sizeof(reachable));
for(int i = 1; i <= n; i++){
maximize(mx, a[i]);
}
dfs(1, -1);
// for(int i = 1; i <= n; i++){
// cout << "NODE: " << i << endl;
// for(int j = 1; j <= mx; j++){
// for(int k = 1; k <= mx; k++){
// if (dp[i][j][k] and j <= a[i] and a[i] <= k) cout << j << ' ' << k << endl;
// }
// }
// }
int ans = 0;
for(int i = 1; i <= mx; i++){
for(int j = i; j <= mx; j++){
if (dp[1][i][j] and i <= a[1] and a[1] <= j) ans++;
}
}
cout << ans << endl;
}
}
namespace subtask2{
bool checkSubtask2(){
return true;
}
int mx;
bitset<102> dp[10004][102];
bitset<102> reachable[102];
void dfs(int u, int p){
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
dfs(v, u);
}
for(int i = 1; i <= mx; i++){
reachable[i].reset();
}
for(auto id: g[u]){
int v = edge[id].se + edge[id].fi - u;
if (v == p) continue;
for(int j = 1; j <= mx; j++){
for(int k = j; k <= mx; k++){
if (dp[v][j][k] and j <= a[v] and a[v] <= k) {
reachable[j][k] = true;
}
}
}
}
for(int i = mx; i >= 1; i--){
if (i == a[u]){
dp[u][a[u]][a[u]] = true;
dp[u][a[u]] |= dp[u][a[u] + 1];
}
if (i > a[u]){
for(int j = i; j <= mx; j++){
if (reachable[i][j]) {
dp[u][i][j] = true;
dp[u][i] |= dp[u][j + 1];
}
}
}
if (i < a[u]){
for(int j = i; j < a[u]; j++){
if (reachable[i][j]){
dp[u][i] |= dp[u][j + 1];
}
}
}
}
}
void solveSubtask2(){
for(int i = 1; i <= n; i++){
maximize(mx, a[i]);
}
dfs(1, -1);
// for(int i = 1; i <= n; i++){
// cout << "NODE: " << i << endl;
// for(int j = 1; j <= mx; j++){
// for(int k = 1; k <= mx; k++){
// if (dp[i][j][k] and j <= a[i] and a[i] <= k) cout << j << ' ' << k << endl;
// }
// }
// }
int ans = 0;
for(int i = 1; i <= mx; i++){
for(int j = i; j <= mx; j++){
if (dp[1][i][j] and i <= a[1] and a[1] <= j) ans++;
}
}
cout << ans << endl;
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin >> n;
FOR(i, 1, n){
cin >> a[i];
}
FOR(i, 1, n - 1){
int u, v;
cin >> u >> v;
edge[i] = {u, v};
g[u].pb(i);
g[v].pb(i);
}
if (subtask1::checkSubtask1()) return subtask1::solveSubtask1(), 0;
if (subtask2::checkSubtask2()) return subtask2::solveSubtask2(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
Compilation message
uzastopni.cpp:203:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
203 | main()
| ^~~~
uzastopni.cpp: In function 'int main()':
uzastopni.cpp:207:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
207 | freopen(TASKNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:208:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
208 | freopen(TASKNAME".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4220 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4188 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4028 KB |
Output is correct |
| 7 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 8 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 9 |
Correct |
3 ms |
4440 KB |
Output is correct |
| 10 |
Correct |
2 ms |
4188 KB |
Output is correct |
| 11 |
Correct |
10 ms |
17244 KB |
Output is correct |
| 12 |
Correct |
9 ms |
17244 KB |
Output is correct |
| 13 |
Correct |
7 ms |
17244 KB |
Output is correct |
| 14 |
Correct |
94 ms |
17932 KB |
Output is correct |
| 15 |
Correct |
97 ms |
18004 KB |
Output is correct |
| 16 |
Correct |
94 ms |
17880 KB |
Output is correct |
| 17 |
Correct |
8 ms |
17244 KB |
Output is correct |
| 18 |
Correct |
7 ms |
17244 KB |
Output is correct |
| 19 |
Correct |
89 ms |
17236 KB |
Output is correct |
| 20 |
Correct |
89 ms |
17172 KB |
Output is correct |
