#include <bits/stdc++.h>
using namespace std;
struct Edge
{
uint64_t u, v, w;
};
vector<vector<uint64_t>> g, anc;
vector<uint64_t> height, ind;
vector<vector<Edge>> unpaved;
vector<vector<uint64_t>> dp;
uint64_t lift(uint64_t u, uint64_t h)
{
uint64_t z = 0;
while (h)
{
if (h & 1)
{
assert(z < anc[u].size());
u = anc[u][z];
}
h >>= 1;
z++;
}
return u;
}
uint64_t lca(uint64_t u, uint64_t v)
{
assert(u < g.size() && v < g.size());
if (height[u] < height[v])
swap(u, v);
u = lift(u, height[u] - height[v]);
if (u == v)
return u;
for (uint64_t i = anc[u].size() - 1; i < anc[u].size(); i--)
{
if (anc[u][i] != anc[v][i])
{
u = anc[u][i];
v = anc[v][i];
}
}
return anc[u][0];
}
void traverse(uint64_t u, vector<uint64_t> &path, uint64_t p = -1, uint64_t h = 0)
{
for (uint64_t i = 1; i <= path.size(); i <<= 1ULL)
anc[u].push_back(path[path.size() - i]);
height[u] = h;
path.push_back(u);
for (uint64_t const &v : g[u])
if (v != p)
traverse(v, path, u, h + 1);
path.pop_back();
}
void calc_dp(uint64_t u)
{
for (uint64_t const &v : g[u])
{
calc_dp(v);
assert(dp[v].size() == (1ULL << g[v].size()));
}
dp[u] = vector<uint64_t>(1ULL << g[u].size());
// Case 1. Just delete the root and add up subtree values.
for (uint64_t z = 0; z < (1ULL << g[u].size()); z++)
{
dp[u][z] = 0;
for (uint64_t i = 0; i < g[u].size(); i++)
{
if (!(z & (1ULL << i)))
{
dp[u][z] += dp[g[u][i]][0];
}
}
}
for (uint64_t i = 0; i < g[u].size(); i++)
{
ind[g[u][i]] = i;
}
// Case 2: Take exactly one unpaved road whose tree path contains u.
for (auto const &[a, b, w] : unpaved[u])
{
// Stores just the value obtained from the two used subtrees.
uint64_t x = 0;
if (a != u)
{
x += dp[a][0];
assert(anc[a].size());
uint64_t r = a, s = anc[a][0];
while (s != u)
{
// assert(dp[s].size() == 1ULL << g[s].size());
x += dp[s][1ULL << ind[r]];
r = s;
s = anc[s][0];
}
}
if (b != u)
{
x += dp[b][0];
uint64_t r = b, s = anc[b][0];
while (s != u)
{
x += dp[s][1ULL << ind[r]];
r = s;
s = anc[s][0];
}
}
uint64_t p = UINT_MAX, q = UINT_MAX;
if (a != u)
p = ind[lift(a, height[a] - height[u] - 1)];
if (b != u)
q = ind[lift(b, height[b] - height[u] - 1)];
for (uint64_t z = 0; z < (1ULL << g[u].size()); z++)
{
if ((a != u && (z & (1ULL << p))) || (b != u && (z & (1ULL << q))))
continue;
uint64_t y = 0;
// Sum all children not on an edge path and not ruled out.
for (uint64_t i = 0; i < g[u].size(); i++)
{
if (!(z & (1ULL << i)) && i != p && i != q)
{
y += dp[g[u][i]][0];
}
}
dp[u][z] = max(dp[u][z], x + y + w);
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, m;
cin >> n >> m;
g = vector<vector<uint64_t>>(n);
vector<Edge> unpaved_edges;
uint64_t total_cost = 0;
for (size_t i = 0; i < m; i++)
{
uint64_t u, v, w;
cin >> u >> v >> w;
total_cost += w;
if (!w)
{
g[u - 1].push_back(v - 1);
g[v - 1].push_back(u - 1);
}
else
{
unpaved_edges.push_back({u - 1, v - 1, w});
}
}
height = vector<uint64_t>(n);
anc = vector<vector<uint64_t>>(n);
vector<uint64_t> path;
traverse(0, path);
for (uint64_t u = 0; u < n; u++)
{
for (auto it = g[u].begin(); it != g[u].end(); it++)
{
if (!anc[u].empty() && *it == anc[u][0])
{
g[u].erase(it);
break;
}
}
}
unpaved = vector<vector<Edge>>(n);
for (auto const &[u, v, w] : unpaved_edges)
{
if (!((height[u] + height[v]) & 1))
{
assert(lca(u, v) < n);
unpaved[lca(u, v)].push_back({u, v, w});
}
}
dp = vector<vector<uint64_t>>(n);
ind = vector<uint64_t>(n);
calc_dp(0);
cout << total_cost - dp[0][0] << '\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 |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
1236 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
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 |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1364 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
1548 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
