给你一个 $n$ 个点 $m$ 条边的无重边的图满足每个点的度数小于等于 $10$，其中有一棵生成树，非树边有边权。删掉若干非树边满足图中不存在长度为偶数的环，求删除的边的代价之和的最小值。

数据范围：$2\leq n\leq 10^3$，$n-1\leq m\leq 5\times 10^3$，$\operatorname{deg}(u)\leq 10$，边权 $1\leq c\leq 10^4$。

首先将问题转换为选择一些非树边加上使得加上的边权最大。容易发现若一条非树边的两端点的距离是奇数，则该边可以直接忽略。

注意到，若两条非树边连接的两个点在树上的路径有重叠，则一定可以构成一个长度为偶数的环，所以不能选择路径重复的边。

考虑动态规划，$f(u,S)$ 表示在以 $u$ 为根节点的子树中的非树边中选择，集合 $S$ 中的儿子节点到 $u$ 的边已经被路径覆盖，此时的最大边权总和。

转移时，把每条非树边挂到两端点的 LCA 上，在 LCA 处一起处理。对每条非树边两端点所在的子树为 $u,v$，都用 $S\cup\{u,v\}$ 去更新 $S$ 的状态。而更新要保证路径上每条边都不能被覆盖过，所以用两端点暴力往 LCA 跳，累加不覆盖此边的状态的和。

由于每条非树边只会被跳最多一次，时间复杂度 $O(nm)$。状态转移在每个结点处初始化一次，每条非树边处更新一次，时间复杂度 $O\left((n+m)2^{10}\right)$。总时间复杂度 $O\left(nm+(n+m)2^{10}\right)$。

/**
 * @date: 2024.01.23
 * @problem: P4649, BZOJ1808
 * @tags: 图论, 动态规划, 树形动态规划, 状态压缩动态规划
 */

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<pair<pair<int,int>,int> > edge;
vector<int> E[1001];
vector<int> toHandle[1001];

int dep[1001],fa[1001][11];
void dfs(int id,int father){
    dep[id]=dep[father]+1;
    fa[id][0]=father;
    for(int k=1;k<=10;k++)
        fa[id][k]=fa[fa[id][k-1]][k-1];
    for(int v :E[id]){
        if(v==father)continue;
        dfs(v,id);
    }
}

inline int getlca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    for(int i=10;i>=0;i--)
        if(dep[u]-dep[v]>=(1<<i))
            u=fa[u][i];
    if(u==v)return u;
    for(int i=10;i>=0;i--)
        if(fa[u][i]!=fa[v][i])
            u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

int f[1001][1<<10],idx[1001];
void dp(int id,int father){
    int cntSon=0;
    for(int v :E[id]){
        if(v==father)continue;
        dp(v,id);
        idx[v]=cntSon++;
    }
    for(int status=0;status<(1<<cntSon);status++)
        for(int v :E[id]){
            if(v==father)continue;
            if(!(status&(1<<idx[v])))f[id][status]+=f[v][0];
        }
    for(int e :toHandle[id]){
        int u=edge[e].first.first;
        int v=edge[e].first.second;
        int w=edge[e].second;
        if(u!=id){
            w+=f[u][0];
            while(fa[u][0]!=id){
                w+=f[fa[u][0]][1<<idx[u]];
                u=fa[u][0];
            }
        }
        if(v!=id){
            w+=f[v][0];
            while(fa[v][0]!=id){
                w+=f[fa[v][0]][1<<idx[v]];
                v=fa[v][0];
            }
        }
        for(int status=0;status<(1<<cntSon);status++){
            int tar=status;
            if(u!=id){
                if(status&(1<<idx[u]))continue;
                tar|=1<<idx[u];
            }
            if(v!=id){
                if(status&(1<<idx[v]))continue;
                tar|=1<<idx[v];
            }
            f[id][status]=max(f[id][status],f[id][tar]+w);
        }
    }
}

int main(){
    scanf("%d%d",&n,&m);
    int sum=0;
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        if(w==0){
            E[u].push_back(v);
            E[v].push_back(u);
        }
        else edge.push_back({{u,v},w}),sum+=w;
    }
    dfs(1,0);
    for(int i=0;i<edge.size();i++){
        int u=edge[i].first.first,v=edge[i].first.second;
        int lca=getlca(u,v);
        if(!((dep[u]+dep[v])&1))toHandle[lca].push_back(i);
    }
    dp(1,0);
    printf("%d\n",sum-f[1][0]);
    return 0;
}