#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct chash {
const uint64_t C = uint64_t(4e18 * acos(0)) + 71;
const uint64_t RANDOM = chrono::steady_clock::now().time_since_epoch().count();
ll operator()(const uint64_t x) const {
return __builtin_bswap64((x ^ RANDOM) * C);
}
};
template <class T> T chmax(T &a, const T b) {
return a = max(a, b);
}
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int N, M;
cin >> N >> M;
vt<vt<int>> adj(N);
vt<ari3> edges;
int tot = 0;
FOR(_, 1, M) {
int a, b, c;
cin >> a >> b >> c, a--, b--;
tot += c;
if (c)
edges.push_back({a, b, c});
else {
adj[a].push_back(b);
adj[b].push_back(a);
}
}
vt<int> depth(N), parent(N);
const auto dfs_depth = [&](auto &&self, const int i, const int p) -> void {
parent[i] = p;
int bad = -1;
FOR(j, 0, size(adj[i]) - 1) {
if (adj[i][j] == p)
bad = j;
else {
depth[adj[i][j]] = depth[i] + 1;
self(self, adj[i][j], i);
}
}
if (bad >= 0)
adj[i].erase(adj[i].begin() + bad);
};
dfs_depth(dfs_depth, 0, -1);
const auto lca = [&](int a, int b) {
for (; depth[a] > depth[b]; a = parent[a]);
for (; depth[b] > depth[a]; b = parent[b]);
for (; a != b; a = parent[a], b = parent[b]);
return a;
};
vt<vt<ari3>> sweep(N);
for (const auto &[a, b, c] : edges)
if (depth[a] + depth[b] + 1 & 1)
sweep[lca(a, b)].push_back({a, b, c});
vt<vt<int>> dp(N);
vt<int> max_dp(N);
vt<unordered_map<int, int, chash>> inds(N);
const auto dfs = [&](auto &&self, const int i, const int p) -> void {
dp[i].assign(1 << size(adj[i]), 0);
FOR(j, 0, size(adj[i]) - 1) {
inds[i][adj[i][j]] = j;
self(self, adj[i][j], i);
}
for (auto [a, b, c] : sweep[i]) {
int v = c + (a != i) * max_dp[a];
for (; a != i && parent[a] != i; a = parent[a])
v += dp[parent[a]][size(dp[parent[a]]) - 1 - (1 << inds[parent[a]][a])];
v += (b != i) * max_dp[b];
for (; b != i && parent[b] != i; b = parent[b])
v += dp[parent[b]][size(dp[parent[b]]) - 1 - (1 << inds[parent[b]][b])];
chmax(dp[i][(a != i ? 1 << inds[i][a] : 0) | (b != i ? 1 << inds[i][b] : 0)], v);
}
FOR(j, 1, size(dp[i]) - 1) {
int v = 0;
FOR(k, 0, size(adj[i]) - 1)
if (j >> k & 1)
v += max_dp[adj[i][k]];
chmax(dp[i][j], v);
}
FOR(j, 1, size(dp[i]) - 1)
for (int k = j; k; k = (k - 1) & j)
chmax(max_dp[i], chmax(dp[i][j], dp[i][k] + dp[i][j ^ k]));
};
dfs(dfs, 0, -1);
cout << tot - *max_element(all(max_dp)) << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |