#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;
constexpr int maxn = 1e3 + 5, maxm = 5e3;
int dp[maxn][1 << 10] = { 0 };
int parent[maxn] = { 0 };
basic_string <int> chld[maxn];
arrr edges[maxm];
basic_string<int>adj[maxn];
arr order[maxn] = { 0 };
int order_to_pos[maxn * 2 + 5] = { 0 };
int depth[maxn] = { 0 };
int t = 0;
void fnd_tree(int p, int par, int dep)
{
depth[p] = dep;
// order_to_pos[t] = p;
order[p][0] = t++;
for (int i : adj[p])
{
if (i == par) continue;
chld[p].push_back(i);
parent[i] = p;
fnd_tree(i, p, dep + 1);
}
order_to_pos[t] = p;
order[p][1] = t++;
}
arr calc_upwards(int p, int fin, int fr)
{
if (p == fin && p == fr) return {0, (int)chld[p].size()};
int ind = 0;
for (int i : chld[p])
{
if (i == fr) break;
ind++;
}
if (p == fin) return {0, ind};
arr r = calc_upwards(parent[p], fin, p);
r[0] += (p == fr ? dp[p][(1 << (chld[p].size())) - 1] : dp[p][(1 << (chld[p].size())) - (1 << ind) - 1]);
return r;
}
priority_queue<arrr, vector<arrr>, greater<arrr>> forw, backw;
void dfs(int p)
{
vector<arrr> new_edges;
for (int i : chld[p])
{
while (!backw.empty() && backw.top()[0] <= order[p][1])
{
new_edges.emplace_back(backw.top());
backw.pop();
}
dfs(i);
}
while (!backw.empty() && backw.top()[0] <= order[p][1])
{
new_edges.emplace_back(backw.top());
backw.pop();
}
int s = chld[p].size();
vector<vector<int>>opt_edges(s + 1, vector<int>(s + 1));
for (int i = 0; i < s; i++)
{
opt_edges[i][s] = dp[chld[p][i]][(1 << (chld[chld[p][i]].size())) - 1];
for (int j = i + 1; j < s; j++)
{
opt_edges[i][j] = dp[chld[p][i]][(1 << (chld[chld[p][i]].size())) - 1] + dp[chld[p][j]][(1 << (chld[chld[p][j]].size())) - 1];
}
}
auto it = new_edges.begin();
arr l, r;
arrr a;
while (it != new_edges.end())
{
a = *it++;
a[0] = order_to_pos[a[0]];
l = calc_upwards(a[0], p, a[0]),
r = calc_upwards(a[1], p, a[1]);
if (l[1] > r[1]) swap(l, r);
opt_edges[l[1]][r[1]] = max(
opt_edges[l[1]][r[1]],
l[0] + r[0] + a[2]
);
}
// Bitset dp
for (int i = 1; i < (1 << s); i++)
{
for (int j = 0; j < s; j++)
{
if ((i & (1 << j)) == 0) continue;
dp[p][i] = max(dp[p][i], dp[p][i - (1 << j)] + opt_edges[j][s]);
for (int k = j + 1; k < s; k++)
{
if ((i & (1 << k)) == 0) continue;
dp[p][i] = max(dp[p][i], dp[p][i - (1 << j) - (1 << k)] + opt_edges[j][k]);
}
}
// if (__builtin_popcount(i) == 1) cout << "\n";
// cout << i << " " << dp[p][i] << "\t";
}
// cout << "\n";
// Return new edges
while (!forw.empty() && forw.top()[0] == order[p][1])
{
a = forw.top();
forw.pop();
a[0] = order_to_pos[a[0]];
swap(a[0], a[1]);
a[0] = order[a[0]][1];
backw.push(a);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
}
sort(edges, edges + m, [](const auto &l, const auto &r) {
return l[2] < r[2];
});
for (int i = 0; i < n - 1; i++)
{
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
fnd_tree(1, 0, 0);
int output = 0;
for (int i = n - 1; i < m; i++)
{
output += edges[i][2];
if ((depth[edges[i][0]] ^ depth[edges[i][1]]) & 1) {
continue;
}
if (order[edges[i][0]][1] > order[edges[i][1]][1]) swap(edges[i][0], edges[i][1]);
edges[i][0] = order[edges[i][0]][1];
forw.push(edges[i]);
}
dfs(1);
cout << output - dp[1][(1 << (chld[1].size())) - 1] << "\n";
assert(output >= 0);
assert(forw.empty());
assert(backw.empty());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
392 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
528 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4636 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4640 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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
852 KB |
Output is correct |
| 2 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
924 KB |
Output is correct |
| 2 |
Correct |
2 ms |
852 KB |
Output is correct |
| 3 |
Correct |
3 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2132 KB |
Output is correct |
| 2 |
Correct |
6 ms |
1224 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
864 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1620 KB |
Output is correct |
| 3 |
Correct |
15 ms |
4580 KB |
Output is correct |
| 4 |
Correct |
5 ms |
1828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
2208 KB |
Output is correct |
| 2 |
Correct |
13 ms |
4564 KB |
Output is correct |
| 3 |
Correct |
8 ms |
1748 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1492 KB |
Output is correct |
