自动搬运

查看原文

来自洛谷，原作者为

	ix35 垒球

搬运于2025-08-24 21:38:09，当前版本为作者最后更新于2020-03-22 09:16:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道仙人掌上 DP 的题。

首先是 Tarjan 找环，然后对环上 DP 和树上 DP 分别讨论：

设 $dp(i,0)$ 表示选了 $i$ 时 $i$ 的子树最大贡献，$dp(i,1)$ 表示选了 $i$ 的某个儿子时 $i$ 的子树的最大贡献，$dp(i,2)$ 表示 $i$ 和儿子都没选时子树的最大贡献。

树上 DP 部分：

设 $v$ 为 $u$ 的子结点，则先令 $dp(u,0)=HX_u$，然后转移：

$dp(v,2)\to dp(u,0)$

$\max(dp(v,1),dp(v,2))\to dp(u,2)$

而 $dp(u,1)$ 略微麻烦。因为只能选恰好一个儿子，别的儿子都按照 $dp(u,2)$ 的方式转移，只有一个儿子是通过 $dp(v,0)$ 的形式转移的，所以只需要统计相对于 $dp(u,2)$ 的增量即可，即：

$dp(u,1)=dp(u,2)+\max(dp(v,0)-\max(dp(v,1),dp(v,2))$

环上 DP 部分：

计算环顶 DP 的值，设环顶为 $u$，环上的点按深度从大到小依次为 $v_1,\ldots,v_k$，那么 $u=v_k$，考虑转移：

先定义一个 $Calc(l,r)$， 表示如果规定了 $v_l$ 和 $v_r$ 不能选，中间的点只要按照规则可以随便选，那么最大的总 DP 值为多少，这就是个链上的 DP，和树上 DP 转移相似。

对于 $dp(u,0)$，增量为 $dp(v_{k-1},2)+dp(v_1,2)+Calc(3,k-3)$。

对于 $dp(u,2)$，增量为 $Calc(2,k-2)$。

对于 $dp(u,1)$，要分类讨论：

1. 选择了环外子结点，那么 $dp(u,1)+Calc(2,k-2)\to dp(u,1)$；

2. 选择了 $v_1$，那么 $dp(u,2)+dp(v_2,2)+dp(v_1,0)+Calc(4,k-2)$；

3. 选择了 $v_{k-1}$，那么 $dp(u,2)+dp(v_{k-2},2)+dp(v_{k-1},0)+Calc(2,k-4)$。

代码，请勿直接抄袭：

#include <bits/stdc++.h>
using namespace std;
const int MAXN=2000010;
int n,m,x,y,eg,ans,tot,h[MAXN],hd[MAXN],ver[2*MAXN],nx[2*MAXN],dfn[MAXN],low[MAXN],f[MAXN],dp[MAXN][3];
int rg[MAXN],tmp[MAXN][3];
void add_edge (int x,int y) {
	ver[++eg]=y;
	nx[eg]=hd[x];
	hd[x]=eg;
	return;
}
int get_dp (int l,int r) {
	tmp[l-1][0]=0,tmp[l-1][1]=dp[rg[l-1]][1],tmp[l-1][2]=dp[rg[l-1]][2];
	for (int i=l;i<=r+1;i++) {
		tmp[i][0]=tmp[i-1][2]+dp[rg[i]][0];
		tmp[i][2]=max(tmp[i-1][1],tmp[i-1][2])+dp[rg[i]][2];
		tmp[i][1]=max(tmp[i-1][0]+dp[rg[i]][2],max(tmp[i-1][1],tmp[i-1][2])+dp[rg[i]][1]);
	}
	//cout << l << "  " << r << "  " << max(tmp[r+1][1],tmp[r+1][2]) << endl;
	return max(tmp[r+1][1],tmp[r+1][2]);
}
void solve (int s,int t) {
	int cnt=0;
	rg[++cnt]=s;
	while (rg[cnt]!=t) {
		rg[cnt+1]=f[rg[cnt]];
		cnt++;
	}
	dp[t][1]=max(dp[t][1]+get_dp(2,cnt-2),dp[t][2]+max(dp[rg[1]][0]+dp[rg[2]][2]+get_dp(4,cnt-2),dp[rg[cnt-1]][0]+dp[rg[cnt-2]][2]+get_dp(2,cnt-4)));
	dp[t][0]+=get_dp(3,cnt-3)+dp[rg[1]][2]+dp[rg[cnt-1]][2];
	dp[t][2]+=get_dp(2,cnt-2);
	return;
}
void dfs (int x,int fa) {
	f[x]=fa,dfn[x]=low[x]=++tot,dp[x][0]=h[x],dp[x][2]=0;
	int tmp=0;
	for (int i=hd[x];i;i=nx[i]) {
		if (!dfn[ver[i]]) {
			dfs(ver[i],x);
			low[x]=min(low[x],low[ver[i]]);
		} else if (ver[i]!=fa) {
			low[x]=min(low[x],dfn[ver[i]]);
		}
		if (low[ver[i]]>dfn[x]) {
			dp[x][0]+=dp[ver[i]][2];
			dp[x][2]+=max(dp[ver[i]][2],dp[ver[i]][1]);
			tmp=max(tmp,dp[ver[i]][0]-max(dp[ver[i]][2],dp[ver[i]][1]));
		}
	}
	dp[x][1]=dp[x][2]+tmp;
	//cout << x << "  " << dp[x][0] << "  " << dp[x][1] << "  " << dp[x][2] << endl;
	for (int i=hd[x];i;i=nx[i]) {
		if (low[ver[i]]==dfn[x]&&f[ver[i]]!=x) {solve(ver[i],x);}
	}
	//cout << x << "  " << dp[x][0] << "  " << dp[x][1] << "  " << dp[x][2] << endl;
	return;
}
int main () {
	freopen("city.in","r",stdin);
	freopen("city.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) {
		if (!dfn[i]) {
			dfs(i,0);
			ans+=max(dp[i][0],max(dp[i][1],dp[i][2]));
		}
	}
	printf("%d\n",ans);
	return 0;
}