#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define sz(x) ll(x.size())
#define N 100015
#define base 1000000
#define M ll(1e9+7)
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef short int si;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int a[5002], h[5002], tin[5002], out[5002], in[5002], id, t[N][15], logs[N], pred[5002], pred_sum[5002], n;
ll ost[5002], dp[5002];
vector <int> vr;
bool can[5002];
ll ans;
vector <pair <int, int> > g[N];
vector <int> gr[5002];
ll calc(int v, int to, ll cur, ll mx, int p)
{
if (v == to) return mx;
cur -= a[v];
for (auto it : g[v])
{
if (it.F == p) continue;
if (!(in[it.F] <= in[to] && out[to] <= out[it.F])) continue;
return calc(it.F, to, cur, mx + max(0ll, cur + it.S), v);
}
}
void go(int v, int from, ll cur)
{
while (cur <= 0 && v != 0)
{
cur -= a[v];
if (v != from) {can[v] = 1; ost[v] = abs(cur);}
cur += pred_sum[v];
v = pred[v];
}
}
void dfs(int v, int p)
{
if (p != -1) h[v] = h[p] + 1;
tin[v] = sz(vr);
in[v] = id++;
vr.pb(v);
for (auto it : g[v])
{
if (p == it.F) continue;
pred[it.F] = v;
pred_sum[it.F] = it.S;
dfs(it.F, v);
vr.pb(v);
gr[v].pb(it.F);
for (auto itr : gr[it.F]) gr[v].pb(itr);
}
out[v] = id++;
vr.pb(v);
}
int lca(int a, int b)
{
if (tin[a] > tin[b]) swap(a, b);
int j = logs[tin[b] - tin[a] + 1];
int v = t[tin[a]][j];
int vt = t[tin[b] - (1 << j) + 1][j];
if (h[v] > h[vt]) return vt;
return v;
}
void rec(int v, ll cur, ll mx, int p)
{
cur -= a[v];
dp[v] = mx;
for (auto it : g[v])
{
if (it.F == p) continue;
rec(it.F, cur, mx + max(0ll, cur + it.S), v);
}
}
void recr(int v, int p)
{
memset(can, 0, sizeof(can));
memset(ost, 0, sizeof(ost));
memset(dp, 0, sizeof(dp));
go(v, v, 0);
rec(v, a[v], 0, p);
for (int i = 1; i <= n; i++)
{
if (i == v) continue;
int lc = lca(v, i);
if (lc != i && lc != v)
{
if (can[lc] && ost[lc] >= calc(lc, i, a[lc], 0, pred[lc])) ans++;
}
else if (lc == i)
{
if (can[i]) ans++;
}
else
{
if (a[v] >= dp[i]) ans++;
}
}
for (auto it : g[v])
{
if (it.F == p) continue;
recr(it.F, v);
}
}
int main()
{
//freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 2; i < N; i++) logs[i] = logs[i >> 1] + 1;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++)
{
int a, b, c;
cin >> a >> b >> c;
g[a].pb({b, c});
g[b].pb({a, c});
}
dfs(1, -1);
int nm = sz(vr) - 1;
for (int i = 0; i <= nm; i++) t[i][0] = vr[i];
for (int j = 1; j < 15; j++)
for (int i = 0; i <= nm; i++)
{
int v = t[i][j - 1];
int vt = t[min(i + (1 << (j - 1)), nm)][j - 1];
if (h[v] > h[vt]) t[i][j] = vt; else t[i][j] = v;
}
recr(1, -1);
cout << ans << endl;
}
Compilation message
transport.cpp: In function 'll calc(int, int, ll, ll, int)':
transport.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
765 ms |
4728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
255 ms |
44920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
6400 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1094 ms |
5124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
6272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
