/*
* First of all, bicolor the tree. Any admissible unpaved edges must connect
* vertexes of the same colour.
*
* Consider each unpaved edge (a, b) the path a->...->b on the tree. A simple
* even cycles exist iff an edge is traversed by two or more paths.
*
* Find the maximal sum of a edge-disjoint subset of the given paths.
*
* dp[v][0] is the maximal sum of edge-disjoint paths in the subtree of v;
* dp[v][1] also comprehend the edge (v, par[v])
*/
#include <bits/stdc++.h>
using namespace std;
struct Lca {
static constexpr int LOG = 10;
int n;
vector<int> dep;
vector<vector<int>> up;
Lca(int _n, const vector<vector<int>>& adj) : n(_n) {
dep.assign(n, 0);
up.assign(n, vector<int>(LOG));
auto dfs = [&](auto&& self, int v, int p) -> void {
up[v][0] = p;
for (int u : adj[v]) {
if (u == p) continue;
dep[u] = dep[v] + 1;
self(self, u, v);
}
};
dfs(dfs, 0, 0);
for (int i = 1; i < LOG; ++i) {
for (int j = 0; j < n; ++j) {
up[j][i] = up[up[j][i-1]][i-1];
}
}
}
int lift(int v, int k) const {
for (int i = LOG-1; i >= 0; --i) {
if (k & (1 << i)) {
v = up[v][i];
}
}
return v;
}
vector<int> get_dep() const { return dep; }
vector<int> get_par() const {
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[i] = up[i][0];
}
return ans;
}
int operator()(int a, int b) const {
if (dep[a] > dep[b]) {
swap(a, b);
}
b = lift(b, dep[b] - dep[a]);
if (a == b) {
return a;
}
for (int i = LOG-1; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
};
int main() {
int n; cin >> n;
int m; cin >> m;
vector<array<int, 3>> e;
vector<vector<int>> adj(n);
for (int i = 0, a, b, c; i < m; ++i) {
cin >> a >> b >> c; --a, --b;
if (c) {
e.push_back({a, b, c});
} else {
adj[a].push_back(b);
adj[b].push_back(a);
}
}
Lca lca(n, adj);
auto dep = lca.get_dep();
auto par = lca.get_par();
vector<vector<array<int, 3>>> paths(n);
for (auto [a, b, c] : e) {
if ((dep[a] & 1) == (dep[b] & 1)) {
paths[lca(a, b)].push_back({a, b, c});
}
}
vector<array<int, 2>> dp(n);
auto find_child = [&](int anc, int v) -> int {
int cur = v;
int prv = -1;
while (cur != anc) {
prv = cur;
cur = par[cur];
}
return prv;
};
auto calc = [&](int anc, int v) -> int {
int ans = 0;
int cur = v;
int prv = -1;
while (prv != anc) {
for (int u : adj[cur]) {
if (u != par[cur] && u != prv) {
ans += dp[u][1];
}
}
prv = cur;
cur = par[cur];
}
return ans;
};
auto dfs = [&](auto&& self, int v) -> void {
for (int u : adj[v]) {
if (u == par[v]) continue;
self(self, u);
}
for (auto [a, b, c] : paths[v]) {
if (a == v || b == v) {
int end = a ^ b ^ v;
int u = find_child(v, end);
dp[u][1] = max(dp[u][1], calc(u, end) + c);
}
}
vector<array<int, 2>> items;
for (auto [a, b, c] : paths[v]) {
if (a == v || b == v) continue;
int aa = find_child(v, a);
int bb = find_child(v, b);
int ia = find(begin(adj[v]), end(adj[v]), aa) - begin(adj[v]);
int ib = find(begin(adj[v]), end(adj[v]), bb) - begin(adj[v]);
assert(0 <= ia && ia < (int)adj[v].size());
assert(0 <= ib && ib < (int)adj[v].size());
int mask = (1 << ia) | (1 << ib);
int inc = c + calc(aa, a) + calc(bb, b) - dp[aa][1] - dp[bb][1];
items.push_back({mask, inc});
// cerr << ia << " " << ib << " " << inc << "\n";
}
int k = adj[v].size();
vector<int> bdp(1 << k);
for (int u : adj[v]) {
if (u == par[v]) continue;
bdp[0] += dp[u][1];
}
for (int mask = 0; mask < (1 << k); ++mask) {
for (auto [tmask, w] : items) {
if ((mask | tmask) == mask) {
bdp[mask] = max(bdp[mask], bdp[mask ^ tmask] + w);
}
}
}
dp[v][0] = *max_element(begin(bdp), end(bdp));
dp[v][1] = dp[v][0];
};
dfs(dfs, 0);
for (int i = 0; i < n; ++i) {
// fprintf(stderr, "dp[%d][0] = %d\tdp[%d][1] = %d\n", i+1, dp[i][0], i+1, dp[i][1]);
}
int ans = 0;
for (auto [_, __, c] : e) {
ans += c;
}
ans -= dp[0][0];
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 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 |
7 ms |
644 KB |
Output is correct |
| 2 |
Correct |
7 ms |
704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 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 |
3 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
