#include<iostream>
#include<random>
#include<chrono>
#include<vector>
#include<algorithm>
#include<queue>
#include<array>
#include<cassert>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
#define pb push_back
#define all(x) x.begin(),x.end()
void solve() {
ll n, m;
cin >> n >> m;
vector<array<ll, 3>> agg;
vector e(n, vector<ll>());
ll ans = 0;
while (m--) {
ll x, y, c;
cin >> x >> y >> c;
x--; y--;
if (c == 0) {
e[x].pb(y);
e[y].pb(x);
} else {
agg.push_back({x, y, c});
ans += c;
}
}
vector bl(n, vector<ll>(20, -1));
vector<ll> depth(n);
vector children(n, vector<ll>());
vector<ll> tin(n), tout(n);
ll cc = 0;
auto dfs = [&](auto dfs, ll g, ll p, ll d) -> void {
bl[g][0] = p;
tin[g] = cc++;
for (int i = 1; i < 20; i++) if (bl[g][i - 1] != -1)
bl[g][i] = bl[bl[g][i - 1]][i - 1];
depth[g] = d;
for (auto u : e[g]) if (u != p) {
dfs(dfs, u, g, d + 1);
children[g].pb(u);
}
tout[g] = cc++;
};
dfs(dfs, 0, -1, 1);
#ifdef LOCAL
cout << "DEPTHS: ";
for (auto u : depth) cout << u << ' ';
cout << '\n';
#endif
auto ancestor = [&](ll x, ll y) -> bool {
if (x == -1) return true;
return tin[x] <= tin[y] and tout[x] >= tout[y];
};
auto lca = [&](ll x, ll y) -> ll {
ll ox = x, oy = y;
assert(x != -1 and y != -1);
if (depth[x] <= depth[y]) swap(x, y);
assert(depth[x] >= depth[y]);
for (int i = 19; i >= 0; i--) {
if (bl[x][i] == -1 or depth[bl[x][i]] < depth[y]) continue;
x = bl[x][i];
}
if (x == y) return x;
for (int i = 19; i >= 0; i--) {
if (bl[x][i] == bl[y][i]) continue;
x = bl[x][i], y = bl[y][i];
}
assert(bl[x][0] != -1);
ll ret = bl[x][0];
assert(ancestor(ret, ox) and ancestor(ret, oy));
return ret;
};
for (int i = 0; i < n; i++)
sort(all(children[i]));
auto get_idx = [&](ll g, ll c) -> ll {
auto iter = lower_bound(all(children[g]), c);
assert(iter != children[g].end() and *iter == c);
return iter - children[g].begin();
};
auto get_ricky = [&](ll root, ll g) -> ll {
assert(ancestor(root, g));
#ifdef LOCAL
cout << "RICKY: " << root << " " << g << " ";
#endif
for (int i = 19; i >=0; i--) {
if (ancestor(bl[g][i], root)) continue;
g = bl[g][i];
}
#ifdef LOCAL
cout << g << '\n';
#endif
return g;
};
vector look(n, vector<array<ll, 3>>());
vector<ll> dp(n);
for (auto [x, y, c] : agg) {
if (depth[x] % 2 != depth[y] % 2) {
continue;
}
look[lca(x, y)].pb({x, y, c});
#ifdef LOCAL
#endif
}
vector dp_st(n, vector<ll>());
auto dfs_2 = [&](auto dfs_2, ll g, ll p) -> ll {
for (auto u : children[g]) dfs_2(dfs_2, u, g);
ll m = (int)children[g].size();
#ifdef LOCAL
#endif
auto& dp_here = dp_st[g];
dp_here.resize(1 << m);
for (int i = 0; i < m; i++) {
ll u = children[g][i];
dp_here[1 << i] = dp[u];
}
for (auto [x, y, c] : look[g]) {
assert(!(x == g and y == g));
if (x == g) swap(x, y);
if (y == g) {
ll rx = get_ricky(g, x);
auto idx = get_idx(g, rx);
ll m2 = (1 << ((int)children[rx].size())) - 1;
if (x != rx) m2 -= (1 << get_idx(rx, get_ricky(rx, x)));
assert(idx < m);
dp_here[1 << idx] = max(dp_here[1 << idx], dp_st[rx][m2] + c);
continue;
}
ll xr = get_ricky(g, x);
ll yr = get_ricky(g, y);
assert(xr != yr);
ll xid = get_idx(g, xr);
ll yid = get_idx(g, yr);
assert(xid != yid);
assert(xid < m and yid < m);
ll b = (1 << yid) | (1 << xid);
#ifdef LOCAL
cout << "Extra edge at: " << g << " abt " << x << ' ' << y << ' ' << "with ids: " << xid << ' ' << yid << " and val: " << c << '\n';
#endif
ll bmx = (1 << ((int)children[xr].size())) - 1;
ll bmy = (1 << ((int)children[yr].size())) - 1;
if (x != xr) bmx -= (1 << get_idx(xr, get_ricky(xr, x)));
if (y != yr) bmy -= (1 << get_idx(yr, get_ricky(yr, y)));
dp_here[b] = max(dp_here[b], dp_st[xr][bmx] + dp_st[yr][bmy] + c);
}
for (int mask = 0; mask < (1 << m); mask++) {
for (int i = 0; i < m; i++) if ((mask >> i) & 1) {
dp_here[mask] = max(dp_here[mask], dp_here[mask ^ (1 << i)] + dp_here[1 << i]);
}
for (int i = 0; i < m; i++) if ((mask >> i) & 1) {
for (int j = i + 1; j < m; j++) if ((mask >> j) & 1) {
int b = (1 << i) | (1 << j);
#ifdef LOCAL
cout << "UPDATING DP... ";
cout << dp_here[mask] << ' ' << dp_here[mask ^ b] + dp_here[b] << '\n';
#endif
dp_here[mask] = max(dp_here[mask], dp_here[mask ^ b] + dp_here[b]);
}
}
}
dp[g] = dp_here[(1 << m) - 1];
return dp[g];
};
ll sub = dfs_2(dfs_2, 0, -1);
#ifdef LOCAL
cout << ans << ' ' << sub << '\n';
#endif
ans -= sub;
cout << ans << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
ll t = 1;
while(t--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
584 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
