#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 dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same_v<T, string>,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
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;
}
}
constexpr ll b_lim = 10;
vector bl(n, vector<ll>(b_lim, -1));
vector<ll> depth(n);
vector children(n, vector<ll>());
vector<ll> tin(n), tout(n);
vector<ll> par(n);
ll cc = 0;
auto dfs = [&](auto dfs, ll g, ll p, ll d) -> void {
bl[g][0] = p;
par[g] = p;
tin[g] = cc++;
for (int i = 1; i < b_lim; 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);
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 = b_lim - 1; 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 = b_lim - 1; 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));
for (int i = b_lim - 1; i >=0; i--) {
if (ancestor(bl[g][i], root)) continue;
g = bl[g][i];
}
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});
}
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();
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);
ll dp_add = 0;
auto start_from_x = [&](ll x) {
ll cx = x;
while (par[cx] != g) {
ll rel_idx = get_idx(par[cx], cx);
ll par_sz = (int)children[par[cx]].size();
ll par_mask = (1 << par_sz) - (1 << rel_idx) - 1;
dp_add += dp_st[par[cx]][par_mask];
cx = par[cx];
}
};
if (y == g) {
dp_add += dp[x];
start_from_x(x);
ll rx = get_ricky(g, x);
auto idx = get_idx(g, rx);
dp_here[1 << idx] = max(dp_here[1 << idx],
dp_add + c);
continue;
}
dp_add += dp[x] + dp[y];
start_from_x(x);
start_from_x(y);
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);
dp_here[b] = max(dp_here[b], dp_add + 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) {
debug(g,mask,i,j);
int b = (1 << i) | (1 << j);
dp_here[mask] = max(dp_here[mask], dp_here[mask ^ b] + dp_here[b]);
}
}
}
assert(dp_here[(1 << m) - 1] == *max_element(all(dp_here)));
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;
}
Compilation message
training.cpp: In instantiation of 'solve()::<lambda(auto:2, ll, ll)> [with auto:2 = solve()::<lambda(auto:2, ll, ll)>; ll = long long int]':
training.cpp:207:32: required from here
training.cpp:22:20: warning: statement has no effect [-Wunused-value]
22 | #define debug(...) "zzz"
| ^~~~~
training.cpp:194:18: note: in expansion of macro 'debug'
194 | debug(g,mask,i,j);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
852 KB |
Output is correct |
| 2 |
Correct |
4 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
596 KB |
Output is correct |
| 2 |
Correct |
3 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
852 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1108 KB |
Output is correct |
| 3 |
Correct |
3 ms |
980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
724 KB |
Output is correct |
| 2 |
Correct |
2 ms |
596 KB |
Output is correct |
| 3 |
Correct |
8 ms |
940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
852 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1080 KB |
Output is correct |
| 3 |
Correct |
9 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
7 ms |
1092 KB |
Output is correct |
