#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 300000
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[3 * 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 |
10 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
8 ms |
11100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
11456 KB |
Output is correct |
| 2 |
Correct |
16 ms |
11612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
18296 KB |
Output is correct |
| 2 |
Correct |
155 ms |
17876 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
247 ms |
21196 KB |
Output is correct |
| 2 |
Correct |
277 ms |
23232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
352 ms |
25284 KB |
Output is correct |
| 2 |
Correct |
419 ms |
30472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
13520 KB |
Output is correct |
| 2 |
Correct |
55 ms |
13284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
15932 KB |
Output is correct |
| 2 |
Correct |
181 ms |
15048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
16832 KB |
Output is correct |
| 2 |
Correct |
229 ms |
17092 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
329 ms |
19144 KB |
Output is correct |
| 2 |
Correct |
306 ms |
19376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
551 ms |
22728 KB |
Output is correct |
| 2 |
Correct |
463 ms |
22472 KB |
Output is correct |
