Description
給定一個n個點m條邊的無向帶權圖，你需要删除若幹條邊，使得這個圖中沒有長度為偶數的簡單環。
有一些邊不能删除，保證不能删除的邊構成原圖的一個生成樹。
n<=1000,m<=5000,每個點的度數<=10
Solution
首先我們把那些本來就能構成偶環的非樹邊删去
接下來考慮剩下的邊，畫一畫能發現如果兩條邊所對應的路徑有交集（邊交），那麼這兩條邊不能同時選
那麼問題就變成了保留一些非樹邊，使得原圖是一個仙人掌的最大邊權。
觀察一下題目的特殊性質，每個點的度數<=10？！
那麼我們可以考慮狀壓，設Fi,s表示點i為根的子樹已經做完了，并且不存在往上的路徑，路徑覆寫的i往兒子連的邊的狀态為s的答案。
那麼考慮某一條路徑，它隻會影響Flca(u,v)！
那麼我們就把它挂在lca處，等到dp到lca再統計它的貢獻。
一條路徑的貢獻？！
就是這條路徑上所有點的可行的最大的F值之和加上這條路徑的權值！
為了友善轉移我們設s的0表示必須被覆寫，1表示可覆寫可不覆寫。
那麼最大值直接用Fi,all轉移就好了
這樣就可以避免用子集合并，不過寫子集合并也不會T就是了
Code
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define pb(x) push_back(x)
using namespace std;
const int N=+,M=*+,T=<<;
int n,m,x,y,z,all,tot,d[N],fa[N],a[N][],id[N][N];
int bel[M],val[M],f[N][T],bit[N];
int t[M*],next[M*],last[N],l;
struct E{int x,y,z;}e[M];
typedef vector<E> vec;
vec w[N];
void add(int x,int y) {t[++l]=y;next[l]=last[x];last[x]=l;}
void travel(int x,int y) {
d[x]=d[y]+;fa[x]=y;
rep(i,x)
if (t[i]!=y) {
travel(t[i],x);
id[x][t[i]]=<<a[x][];
a[x][++a[x][]]=t[i];
}
bit[x]=(<<a[x][])-;
}
int lca(int x,int y) {
if (d[x]<d[y]) swap(x,y);
while (d[x]>d[y]) x=fa[x];
while (x!=y) x=fa[x],y=fa[y];
return x;
}
void Dp(int x) {
fo(i,,a[x][]) Dp(a[x][i]);
if (!w[x].empty())
fo(i,,w[x].size()-) {
int u=w[x][i].x,v=w[x][i].y,now=w[x][i].z;bel[i]=;
if (u!=x) {
now+=f[u][bit[u]];
while (fa[u]!=x) {
now+=f[fa[u]][bit[fa[u]]^id[fa[u]][u]];
u=fa[u];
}
bel[i]+=id[x][u];
}
if (v!=x) {
now+=f[v][bit[v]];
while (fa[v]!=x) {
now+=f[fa[v]][bit[fa[v]]^id[fa[v]][v]];
v=fa[v];
}
bel[i]+=id[x][v];
}
val[i]=now;
}
fo(i,,bit[x]) {
fo(j,,a[x][])
if (i&(<<(j-)))
f[x][i]=f[x][i]+f[a[x][j]][bit[a[x][j]]];
if (!w[x].empty())
fo(j,,w[x].size()-)
if ((bel[j]&i)==bel[j])
f[x][i]=max(f[x][i],f[x][i^bel[j]]+val[j]);
}
}
int main() {
freopen("training.in","r",stdin);
freopen("training.out","w",stdout);
scanf("%d%d",&n,&m);
fo(i,,m) {
scanf("%d%d%d",&x,&y,&z);all+=z;
if (!z) {
add(x,y);
add(y,x);
} else e[++tot].x=x,e[tot].y=y,e[tot].z=z;
}
travel(,);
fo(i,,tot) {
int z=lca(e[i].x,e[i].y);
if ((d[e[i].x]+d[e[i].y]-*d[z])&) continue;
w[z].push_back(e[i]);
}
Dp();
printf("%d\n",all-f[][bit[]]);
}