#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
Phu Trong from Nguyen Tat Thanh High School for gifted student
*/
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {x = y; return 1;}
return 0;
}
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps = 1e-9;
if (x + eps < y) {x = y; return 1;}
return 0;
}
#define MAX 100005
#define N 100000
int numNode;
int label[MAX];
struct Edge{
int u, v, w;
Edge(){}
Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){}
int other(int x){return (x ^ u ^ v);}
} edge[MAX];
vector<int> G[MAX];
int sz[MAX], del[MAX];
int reSubsize(int u, int p = -1){
sz[u] = 1;
for (int&i : G[u]){
int v = edge[i].other(u);
if(v ^ p){
if(del[v]) continue;
reSubsize(v, u);
sz[u] += sz[v];
}
}
return sz[u];
}
int findCentroid(int u, int p, int siz){
for (int &i : G[u]){
int v = edge[i].other(u);
if(v ^ p){
if (!del[v] && 2 * sz[v] > siz) return findCentroid(v, u, siz);
}
}
return u;
}
int F[MAX];
vector<pair<int, int>> rback;
int low_bit(int p){
return p & (-p);
}
void upd(int p, int val){
if (val > 0) rback.emplace_back(p, -val);
for (; p <= N; p += low_bit(p)) F[p] += val;
}
int query(int p){
int res = 0;
for (; p > 0; p -= low_bit(p)) res += F[p];
return res;
}
void undo(void){
while((int)rback.size()){
int p, v; tie(p, v) = rback.back();
upd(p, v);
rback.pop_back();
}
}
template<class T = vector<int>>
void unique(T &v){
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
}
vector<int> comp;
int find(int x){
return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
}
int up[MAX], down[MAX], pref[MAX];
int ans = 0;
void dfs_down(int u, int p, int sm){
comp.push_back(-down[u]);
if(down[u] >= 0) ++ans;
for (int&i : G[u]){
int v = edge[i].other(u);
if(v ^ p){
if (del[v]) continue;
down[v] = min(sm - edge[i].w, down[u]);
dfs_down(v, u, sm + label[v] - edge[i].w);
}
}
}
void dfs_up(int u, int p){
comp.push_back(up[u]);
comp.push_back(pref[u]);
if(up[u] >= 0) ++ans;
for (int &i : G[u]){
int v = edge[i].other(u);
if(v ^ p){
if(del[v]) continue;
pref[v] = pref[u] + label[v] - edge[i].w;
up[v] = min(up[u] + label[v] - edge[i].w, label[v] - edge[i].w);
dfs_up(v, u);
}
}
}
void dfs(int u, int p, bool add){
if(add){
int v = find(-down[u]);
upd(v, 1);
}
else{
int v = find(pref[u]);
if(up[u] >= 0)
ans += query(v);
}
for (int &i : G[u]){
int v = edge[i].other(u);
if(v ^ p){
if(del[v]) continue;
dfs(v, u, add);
}
}
}
void decompose(int root){
int siz = reSubsize(root);
root = findCentroid(root, root, siz);
comp.clear();
del[root] = true;
for (int&i : G[root]) {
int v = edge[i].other(root);
if(del[v]) continue;
down[v] = label[root] - edge[i].w;
dfs_down(v, root, label[root] + label[v] - edge[i].w);
pref[v] = label[v] - edge[i].w;
up[v] = label[v] - edge[i].w;
dfs_up(v, root);
}
sort(comp.begin(), comp.end());
unique(comp);
for (int &i : G[root]){
int v = edge[i].other(root);
if(del[v]) continue;
dfs(v, root, 0);
dfs(v, root, 1);
}
undo();
reverse(G[root].begin(), G[root].end());
for (int &i : G[root]){
int v = edge[i].other(root);
if(del[v]) continue;
dfs(v, root, 0);
dfs(v, root, 1);
}
undo();
for (int&i : G[root]){
int v = edge[i].other(root);
if(del[v]) continue;
decompose(v);
}
}
void process(void){
cin >> numNode;
for (int i = 1; i <= numNode; ++i) cin >> label[i];
for (int i = 1; i < numNode; ++i) {
cin >> edge[i].u >> edge[i].v >> edge[i].w;
G[edge[i].u].emplace_back(i);
G[edge[i].v].emplace_back(i);
}
decompose(1);
cout << ans;
}
signed main(){
#define name "Whisper"
cin.tie(nullptr) -> sync_with_stdio(false);
//freopen(name".inp", "r", stdin);
//freopen(name".out", "w", stdout);
process();
return (0 ^ 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
9052 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
9308 KB |
Output is correct |
| 2 |
Correct |
18 ms |
9776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
158 ms |
17496 KB |
Output is correct |
| 2 |
Correct |
126 ms |
16844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
206 ms |
20804 KB |
Output is correct |
| 2 |
Correct |
263 ms |
23132 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
298 ms |
25708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
12236 KB |
Output is correct |
| 2 |
Correct |
50 ms |
11980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
14792 KB |
Output is correct |
| 2 |
Correct |
165 ms |
14284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
241 ms |
16320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
19648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
476 ms |
24000 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
