#include <stdio.h>
#include <stdlib.h>
#define M 5005
#define N 1005
int n, m, m_, *eh[N], eo[N], dep[N], tin[N], head[N], tout[N];
int *fh[N], fo[N];
void pus_(int **eh, int *eo, int j) {
int o = eo[0]++;
if (0 == o) eh[0] = (int*)malloc(2 * sizeof **eh);
else if (0 == (o & o - 1)) eh[0] = (int*)realloc(eh[0], 2 * o * sizeof**eh);
eh[0][o] = j;
}
#define pus(eh, eo, j) pus_(&(eh), &(eo), j)
int rc[M], ru[M], rv[M], timer, sz[N], par[N], temp;
void dfs(int u, int p) {
sz[u] = 1;
par[u] = p;
for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != p) {
dep[v] = dep[u] + 1;
dfs(v, u);
if (sz[v] > sz[eh[u][0]]) temp = eh[u][0], eh[u][0] = eh[u][j], eh[u][j] = temp;
}
}
void hld(int u) {
tin[u] = timer++;
for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != par[u]) {
head[v] = j ? v : head[u];
hld(v);
}
tout[u] = timer - 1;
}
int lca(int u, int v) {
while (head[u] != head[v]) {
if (dep[head[u]] > dep[head[v]]) u = par[head[u]];
else v = par[head[v]];
}
return dep[u] < dep[v] ? u : v;
}
long long dp[N], dpc[N];
long long st1[N], st2[N];
void add(long long *st, int p, long long k) {
for (st[p += n] += k; p /= 2;)
st[p] = st[p * 2] + st[p * 2 + 1];
}
long long sum(long long *st, int l, int r) {
long long z = 0;
for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
if (l & 1) z += st[l++];
if (r & 1) z += st[--r];
}
return z;
}
long long upqry(long long *st, int u, int a, int off) {
long long z = 0;
for (; head[u] != head[a]; u = par[head[u]])
z += sum(st, tin[head[u]], tin[u]);
z += sum(st, tin[a] + off, tin[u]);
return z;
}
void efs(int u, int p) {
dp[u] = 0;
for (int v, j = 0; j < eo[u]; ++j) if ((v = eh[u][j]) != par[u]) {
efs(v, u);
dp[u] += dp[v];
}
dpc[u] = dp[u];
add(st1, tin[u], dpc[u]);
for (int j = 0; j < fo[u]; ++j) {
int e = fh[u][j];
if (dep[ru[e]] > dep[rv[e]])
temp = ru[e], ru[e] = rv[e], rv[e] = temp;
long long here;
if (tin[ru[e]] <= tin[rv[e]] && tout[rv[e]] <= tout[ru[e]]) {
here = upqry(st1, rv[e], u, 0) - upqry(st2, rv[e], u, 1) + rc[e]
+ dp[rv[e]] - dpc[rv[e]];
} else {
here = upqry(st1, ru[e], u, 0) + upqry(st1, rv[e], u, 1)
- upqry(st2, ru[e], u, 1) - upqry(st2, rv[e], u, 1) + rc[e]
+ dp[rv[e]] - dpc[rv[e]]
+ dp[ru[e]] - dpc[ru[e]];
}
if (here > dp[u]) {
dp[u] = here;
}
}
add(st2, tin[u], dp[u]);
}
int main() {
scanf("%d%d", &n, &m);
for (int u, v, c, i = 0; i < m; ++i) {
scanf("%d%d%d", &u, &v, &c);
if (!c)
pus(eh[u], eo[u], v), pus(eh[v], eo[v], u);
else
ru[m_] = u, rv[m_] = v, rc[m_] = c, ++m_;
}
dfs(1, 1);
head[1] = 1;
hld(1);
long long answer = 0;
for (int i = 0; i < m_; ++i) {
int a = lca(ru[i], rv[i]);
answer += rc[i];
if ((dep[ru[i]] + dep[rv[i]] - 2 * dep[a]) % 2) {
} else {
pus(fh[a], fo[a], i);
}
}
efs(1, 1);
printf("%lld\n", answer - dp[1]);
}
Compilation message
training.c: In function 'pus_':
training.c:14:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
14 | else if (0 == (o & o - 1)) eh[0] = (int*)realloc(eh[0], 2 * o * sizeof**eh);
| ~~^~~
training.c: In function 'main':
training.c:109:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | scanf("%d%d", &n, &m);
| ^~~~~~~~~~~~~~~~~~~~~
training.c:111:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d%d%d", &u, &v, &c);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
