#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});
}
}
constexpr int K = 10;
constexpr int all = (1 << K) - 1;
vector<vector<int>> dp(n, vector<int>(1 << 10));
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 find_id = [&](int v, int u) -> int {
return find(begin(adj[v]), end(adj[v]), u) - begin(adj[v]);
};
auto calc = [&](int anc, int v) -> int {
int ans = dp[v][all];
int cur = par[v];
int prv = v;
while (prv != anc) {
ans += dp[cur][all ^ (1 << find_id(cur, prv))];
prv = cur;
cur = par[cur];
}
return ans;
};
auto dfs = [&](auto&& self, int v) -> void {
for (int u : adj[v]) {
if (u != par[v]) {
self(self, u);
}
}
vector<array<int, 2>> items;
for (auto [a, b, c] : paths[v]) {
if (a == v || b == v) {
int end = a ^ b ^ v;
int u = find_child(v, end);
int i = find_id(v, u);
items.push_back({1 << i, calc(u, end) + c});
} else {
int aa = find_child(v, a);
int bb = find_child(v, b);
int ia = find_id(v, aa);
int ib = find_id(v, bb);
int mask = (1 << ia) | (1 << ib);
int inc = c + calc(aa, a) + calc(bb, b);
items.push_back({mask, inc});
}
}
for (int i = 0; i < (int)adj[v].size(); ++i) {
if (adj[v][i] == par[v]) continue;
items.push_back({1 << i, dp[adj[v][i]][all]});
}
for (int mask = 0; mask < (1 << K); ++mask) {
for (int i = 0; i < K; ++i) {
if (mask & (1 << i)) {
dp[v][mask] = max(dp[v][mask], dp[v][mask ^ (1 << i)]);
}
}
for (auto [tmask, w] : items) {
if ((mask | tmask) == mask) {
dp[v][mask] = max(dp[v][mask], dp[v][mask ^ tmask] + w);
}
}
}
};
dfs(dfs, 0);
for (int i = 0; i < n; ++i) {
// fprintf(stderr, "dp[%d] = %d\n", i+1, dp[i][all]);
}
int ans = 0;
for (auto [_, __, c] : e) {
ans += c;
}
ans -= dp[0][all];
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
428 KB |
Output is correct |
| 2 |
Correct |
4 ms |
424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
4636 KB |
Output is correct |
| 2 |
Correct |
57 ms |
4752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
724 KB |
Output is correct |
| 2 |
Correct |
6 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
1492 KB |
Output is correct |
| 2 |
Correct |
17 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
2408 KB |
Output is correct |
| 2 |
Correct |
29 ms |
2388 KB |
Output is correct |
| 3 |
Correct |
31 ms |
2456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
4680 KB |
Output is correct |
| 2 |
Correct |
64 ms |
4692 KB |
Output is correct |
| 3 |
Correct |
61 ms |
4632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
2460 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2484 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4732 KB |
Output is correct |
| 4 |
Correct |
32 ms |
2516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
73 ms |
4696 KB |
Output is correct |
| 2 |
Correct |
82 ms |
4692 KB |
Output is correct |
| 3 |
Correct |
67 ms |
4956 KB |
Output is correct |
| 4 |
Correct |
60 ms |
4668 KB |
Output is correct |
