#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif
/*
initially misread the problem (thought that only tree edges can be deleted)
then understood that only back edges can be deleted after reading the first few lines of the edi
didnt take any other hints from the edi
non-tree edges with odd length are forcefully deleted
instead of minimizing the sum of deleted edges, maximize the sum of staying edges
key idea:
no 2 non-tree paths can have intersecting edges
i.e each tree edge is contained in at most 1 cycle
(updated this part of the explanation after reading edi, initial explanation was not very clear)
figured out after drawing some cases
process each non-tree edge at its lca
can do bitmask dp
dp[u][mask] = max sum of staying edges if we only look at edges with lca in sub of u and we cant pick any (u,v) that come from subtree of a child that is set in mask
each node has at most 10 edges (so at most 10 subtrees), which allows us to do bitmask dp
refer code for transitions
*/
const int MOD = 1e9 + 7;
const int N = 1e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
vector<ll> adj[N];
struct lca_algo {
// LCA template (for graphs with 1-based indexing)
int LOG = 1;
vector<int> depth;
vector<vector<int>> up;
vector<int> tin, tout;
int timer = 1;
lca_algo() {
}
lca_algo(int n) {
lca_init(n);
}
void lca_init(int n) {
while ((1 << LOG) < n) LOG++;
up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
depth = vector<int>(n + 1);
tin = vector<int>(n + 1);
tout = vector<int>(n + 1);
lca_dfs(1, -1);
}
void lca_dfs(int node, int par) {
tin[node] = timer++;
trav(child, adj[node]) {
if (child == par) conts;
up[child][0] = node;
rep1(j, LOG - 1) {
up[child][j] = up[up[child][j - 1]][j - 1];
}
depth[child] = depth[node] + 1;
lca_dfs(child, node);
}
tout[node] = timer-1;
}
int lift(int u, int k) {
rep(j, LOG) {
if (k & (1 << j)) {
u = up[u][j];
}
}
return u;
}
int query(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
u = lift(u, k);
if (u == v) return u;
rev(j, LOG - 1, 0) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
u = up[u][0];
return u;
}
int get_dis(int u, int v) {
int lca = query(u, v);
return depth[u] + depth[v] - 2 * depth[lca];
}
bool is_ances(int u, int v){
return tin[u] <= tin[v] and tout[u] >= tout[v];
}
};
lca_algo LCA;
vector<array<ll,3>> here[N];
vector<ll> par(N);
ll dp[N][1<<10];
ll adj_pos[N][N];
void dfs1(ll u){
auto &children = adj[u];
ll siz = sz(children);
trav(v,children){
dfs1(v);
}
ll best[siz][siz];
memset(best,-0x3f,sizeof best);
for(auto [x,y,w] : here[u]){
vector<ll> path1,path2;
{
ll i = x;
while(i != u){
path1.pb(i);
i = par[i];
}
}
{
ll i = y;
while(i != u){
path2.pb(i);
i = par[i];
}
}
ll cost = w;
ll jbx = -1, jby = -1;
if(!path1.empty()){
cost += dp[path1[0]][0];
rep1(i,sz(path1)-1){
ll id = adj_pos[path1[i]][path1[i-1]];
cost += dp[path1[i]][1<<id];
}
jbx = path1.back();
}
if(!path2.empty()){
cost += dp[path2[0]][0];
rep1(i,sz(path2)-1){
ll id = adj_pos[path2[i]][path2[i-1]];
cost += dp[path2[i]][1<<id];
}
jby = path2.back();
}
assert(!(jbx == -1 and jby == -1));
if(jbx == -1) jbx = jby;
if(jby == -1) jby = jbx;
jbx = adj_pos[u][jbx];
jby = adj_pos[u][jby];
amax(best[jbx][jby],cost);
}
rep(i,siz){
ll v = children[i];
amax(best[i][i],dp[v][0]);
}
rev(mask,(1<<siz)-1,0){
rep(x,siz){
if(mask&(1<<x)) conts;
rep(y,siz){
if(mask&(1<<y)) conts;
amax(dp[u][mask],best[x][y]+dp[u][mask|(1<<x)|(1<<y)]);
}
}
}
}
void solve(int test_case)
{
ll n,m; cin >> n >> m;
vector<array<ll,3>> edges;
rep1(i,m){
ll u,v,w; cin >> u >> v >> w;
if(!w){
adj[u].pb(v), adj[v].pb(u);
}
else{
edges.pb({u,v,w});
}
}
LCA = lca_algo(n);
ll sum = 0;
for(auto [u,v,w] : edges){
sum += w;
if((LCA.depth[u]&1) != (LCA.depth[v]&1)) conts;
ll lca = LCA.query(u,v);
here[lca].pb({u,v,w});
}
rep1(i,n){
par[i] = LCA.up[i][0];
}
for(int i = 2; i <= n; ++i){
adj[i].erase(find(all(adj[i]),par[i]));
}
rep1(i,n){
sort(all(adj[i]));
}
rep1(u,n){
ll ptr = 0;
trav(v,adj[u]){
adj_pos[u][v] = ptr++;
}
}
dfs1(1);
ll ans = sum-dp[1][0];
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
// cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
604 KB |
Output is correct |
| 2 |
Correct |
1 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
8 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2652 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2648 KB |
Output is correct |
| 2 |
Correct |
1 ms |
2652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4956 KB |
Output is correct |
| 2 |
Correct |
1 ms |
5208 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
8 ms |
9560 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
3 ms |
5980 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12768 KB |
Output is correct |
| 4 |
Correct |
4 ms |
5980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
10836 KB |
Output is correct |
| 2 |
Correct |
15 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
9 ms |
10272 KB |
Output is correct |
| 4 |
Correct |
7 ms |
9772 KB |
Output is correct |
