#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();
}
// Finding max without using this node
for (int i: chld[p]) // Going through each child and finding their best
{
dp[p][0] += dp[i][(1 << (chld[i].size())) - 1];
}
int s = chld[p].size();
vector<vector<int>>opt_edges(s + 1, vector<int>(s + 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] - dp[p][0]
);
}
// for (int i = 0; i <= s; i++)
// {
// for (int j = 0; j <= s; j++)
// {
// cout << opt_edges[i][j] << " ";
// }
// cout << "\n";
// }
// 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";
// for (int i = 1; i <= n; i++) cout << dp[i][(1 << (chld[i].size())) - 1] << " ";
// cout << "\n";
// cout << output << "\n";
assert(forw.empty());
assert(backw.empty());
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
4564 KB |
Output is correct |
| 2 |
Correct |
6 ms |
4564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
2132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
852 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
2132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
