洛谷 P4649 题解

$\text{Link}$

思路分析

反面考虑，计算最多能加几条非树边使图上没有偶环

如果某条非树边 $(u,v)$ 添加后使得 $u\to \operatorname{LCA}(u,v)\to v\to u$ 的长度为偶数，则不能必选择 $(u,v)$

只考虑添加 $(u,v)$ 使得 $u\to \operatorname{LCA}(u,v) \to v\to u$ 的长度为奇数的边 $(u,v)$

如果两条边 $(u,v)$ 和 $(x,y)$ 的树上路径有交集，如下图所示，也会形成一个偶环：

所以我们的目标就是在树上选择若干条不相交的非树边使得其权值和最大

考虑在添加某条非树边 $(u,v)$ 后把 $u\to v$ 的所有边都删掉，然后分成若干棵子树进行 dp

我们把每条非树边 $(u,v)$ 在 $\operatorname{LCA}(u,v)$ 处考虑，设 $dp_{p,\mathbf S}$ 表示以 $u$ 为根的子树，且 $p$ 到集合 $\mathbf S$（状态压缩）中的儿子的边已经被删掉后能选择的最优答案

那么对于一条路径 $(u,v)$ 满足 $\operatorname{LCA}(u,v)=p$ 他能带来的价值为：

$$value(u,v)=w(u,v)+\sum_{x\in path(u,v)}^{fa(x)\neq p,x\neq p} dp_{fa(x),\{x\}}$$

设 $u\to v$ 的路径包含 $x\to p\to y$ 且 $x,y$ 均为 $p$ 的儿子，我们可以用用这个价值去转移：

$$\forall \mathbf S:x,y\not\in \mathbf S\\ dp_{p,S}\gets value(u,v)+dp_{p,\mathbf S\cup\{x,y\}}$$

最终的答案为 $\sum w(u,v)-dp_{1,\varnothing}$

时间复杂度 $\Theta(m\log n+n2^{|\mathbf S|})$

总结：

神仙题

观察性质转化成生成仙人掌

然后状压树上 dp

很强

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001;
vector <int> tree[MAXN];
struct node {
	int src,des,val;
};
vector <node> vec,link[MAXN];
int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],root[MAXN],fid[MAXN];
int dp[MAXN][1<<10];
inline int bit(int x) {
	return 1<<x;
}
inline void init1(int p,int f) {
	fa[p]=f,siz[p]=1,dep[p]=dep[f]+1;
	for(int v:tree[p]) {
		if(v==f) continue;
		init1(v,p);
		siz[p]+=siz[v];
		if(siz[v]>siz[son[p]]) son[p]=v;
	}
}
inline void init2(int p,int r) {
	root[p]=r;
	if(son[p]) init2(son[p],r);
	for(int v:tree[p]) {
		if(v==son[p]||v==fa[p]) continue;
		init2(v,v);
	}
}
inline void init3(int p) {
	for(int i=0;i<tree[p].size();++i) {
		int v=tree[p][i];
		if(v==fa[p]) continue;
		fid[v]=bit(i);
		init3(v);
	}
}
inline int LCA(int u,int v) {
	while(root[u]!=root[v]) {
		if(dep[root[u]]<dep[root[v]]) swap(u,v);
		u=fa[root[u]];
	}
	return dep[u]>dep[v]?v:u;
}
inline void dfs(int p) {
	for(int v:tree[p]) {
		if(v==fa[p]) continue;
		dfs(v);
	}
	for(int s=0;s<bit(tree[p].size());++s) {
		for(int i=0;i<tree[p].size();++i) {
			if(!((s>>i)&1)) dp[p][s]+=dp[tree[p][i]][0];
		}
	}
	for(auto e:link[p]) {
		int val=e.val,u=0,v=0;;
		if(e.src!=p) {
			val+=dp[e.src][0];
			for(u=e.src;fa[u]!=p;u=fa[u]) val+=dp[fa[u]][fid[u]];
		}
		if(e.des!=p) {
			val+=dp[e.des][0];
			for(v=e.des;fa[v]!=p;v=fa[v]) val+=dp[fa[v]][fid[v]];
		}
		int t=fid[u]|fid[v];
		for(int s=0;s<bit(tree[p].size());++s) {
			if(!(s&t)) dp[p][s]=max(dp[p][s],val+dp[p][s|t]);
		}
	}
}
signed main() {
	int n,m,res=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		if(!w) {
			tree[u].push_back(v);
			tree[v].push_back(u);
		} else {
			res+=w;
			vec.push_back((node){u,v,w});
		}
	}
	init1(1,0);
	init2(1,1);
	init3(1);
	for(auto e:vec) {
		int lca=LCA(e.src,e.des);
		if(!((dep[e.src]+dep[e.des]-dep[lca]*2)&1)) link[lca].push_back(e);
	}
	dfs(1);
	printf("%d\n",res-dp[1][0]);
	return 0;
}