#include <stdio.h>
#include <stdlib.h>
#define N 100000
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int ij[N], ww[N];
int *eh[N], eo[N], vv[N];
void append(int i, int h) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
eh[i][o] = h;
}
long long ans;
void remove_(int i, int h) {
int o;
for (o = eo[i]; o--; )
if (eh[i][o] == h) {
eo[i]--;
while (o < eo[i])
eh[i][o] = eh[i][o + 1], o++;
}
}
int sz[N], c;
void dfs(int p, int i, int n) {
int o, centroid;
sz[i] = 1, centroid = 1;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
if (j != p) {
dfs(i, j, n);
if (sz[j] * 2 > n)
centroid = 0;
sz[i] += sz[j];
}
}
if ((n - sz[i]) * 2 > n)
centroid = 0;
if (centroid)
c = i;
}
int rr[N]; long long xx[N * 2]; int ii[N * 2], n_;
void dfs_(int r, int p, int i, long long w, long long x, long long y) {
int o;
rr[i] = r;
xx[i << 1 | 0] = x == w ? w - vv[c] : -1, ii[n_++] = i << 1 | 0;
xx[i << 1 | 1] = -y, ii[n_++] = i << 1 | 1;
for (o = eo[i]; o--; ) {
int h = eh[i][o], j = i ^ ij[h];
if (j != p)
dfs_(i == c ? j : r, i, j, w - ww[h] + vv[j], max(x, w - ww[h] + vv[j]), min(y, w - ww[h]));
}
}
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = xx[ii[j]] != xx[i_] ? (xx[ii[j]] > xx[i_] ? -1 : 1) : (ii[j] & 1) - (i_ & 1);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
void cd(int i, int n) {
static int kk[N];
int o, h, j, k;
dfs(-1, i, n), i = c;
n_ = 0;
dfs_(i, -1, i, vv[i], vv[i], 0);
sort(ii, 0, n_);
for (h = 0, k = 0; h < n_; h++) {
int i_ = ii[h];
if ((i_ & 1) == 0)
kk[rr[i_ >> 1]]++, k++;
else
ans += k - kk[rr[i_ >> 1]];
}
for (h = 0; h < n_; h++) {
int i_ = ii[h];
if ((i_ & 1) == 0)
kk[rr[i_ >> 1]]--;
}
for (o = eo[i]; o--; ) {
h = eh[i][o], j = i ^ ij[h];
remove_(j, h), cd(j, sz[j] < sz[i] ? sz[j] : n - sz[i]);
}
}
int main() {
int n, h, i, j;
scanf("%d", &n);
for (i = 0; i < n; i++) {
scanf("%d", &vv[i]);
eh[i] = (int *) malloc(2 * sizeof *eh[i]);
}
for (h = 0; h < n - 1; h++) {
int w;
scanf("%d%d%d", &i, &j, &w), i--, j--;
ij[h] = i ^ j, ww[h] = w;
append(i, h), append(j, h);
}
cd(0, n);
printf("%lld\n", ans);
return 0;
}
Compilation message
transport.c: In function 'append':
transport.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
21 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
transport.c: In function 'main':
transport.c:130:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
transport.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d", &vv[i]);
| ^~~~~~~~~~~~~~~~~~~
transport.c:138:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
138 | scanf("%d%d%d", &i, &j, &w), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
588 KB |
Output is correct |
| 2 |
Correct |
5 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
972 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
8684 KB |
Output is correct |
| 2 |
Correct |
69 ms |
7880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
117 ms |
11944 KB |
Output is correct |
| 2 |
Correct |
122 ms |
13240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
16068 KB |
Output is correct |
| 2 |
Correct |
191 ms |
19628 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
3396 KB |
Output is correct |
| 2 |
Correct |
46 ms |
3084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
5724 KB |
Output is correct |
| 2 |
Correct |
94 ms |
5060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
157 ms |
7400 KB |
Output is correct |
| 2 |
Correct |
153 ms |
7768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
201 ms |
9372 KB |
Output is correct |
| 2 |
Correct |
221 ms |
9772 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
12484 KB |
Output is correct |
| 2 |
Correct |
224 ms |
11164 KB |
Output is correct |
