自动搬运

查看原文

来自洛谷，原作者为

	Stone_Xz 且怒且悲且狂哉 ，且忘且赶且等待

搬运于2025-08-24 22:52:23，当前版本为作者最后更新于2024-04-04 14:28:01，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

传送门：[ICPC2021 Nanjing R] Crystalfly

你说得对，但我不玩原神捏 QWQ

简要题意：

给定一棵 $n$ 个节点的树，每个节点上都有给定数量的晶蝶。每一秒可以移动到相邻的点并拿走这个点的晶蝶。当到达一个点 $u$ 时，与它相邻的点 $v$ 的晶蝶将会在 $t_v$ 秒后逃走。求最多能抓到的晶蝶数量。

思路分析：

我们不妨画一个最简单的树，来思考一下这题。

通过简单思考可以发现，假设当前节点为 $cur$，则如果对于 $cur$ 的子节点 $nxt$，$t_{nxt} < 3$，那么如果去了别的 $cur$ 的儿子节点，$nxt$ 的晶蝶就绝对抓不到了。

但是，在 $t_{nxt} = 3$ 的情况下，还有一种新的抓法：

可以先到另一个儿子节点去，再返回到 $nxt$。

让我们总结一下：设当前节点为 $cur$，有两种抓晶蝶的方案：

• 情况一：不返回 $cur$：只选一个儿子节点为方向去。

• 情况二：返回 $cur$：如果子节点 $nxt$ 的 $t_{nxt} = 3$，可以先走到 $cur$ 别的儿子节点，再通过返回 $cur$ 走过去。

以当前节点 $cur$ 为起点能抓到的最多晶蝶数，取决于以 $cur$ 的子节点 $nxt$ 为起点能抓到的最多晶蝶数，考虑树形 DP。

DP状态：

首先，有两个简单但重要的结论：

• 当走到了点 $cur$，$cur$ 肯定没了。

• 当走到了点 $cur$，$cur$ 的子节点会跑，但孙子节点完全不受影响，一直停着不动，可以随时返回来抓。

当我们想返回时（即情况二），我们首先走到了 $i$，然后返回 $cur$，最后去点 $j$，此时点 $i$ 的子节点都跑了，后面我们来取的时候，为了方便更新，设计二维 DP 状态：

• $dp[i][0]$ 表示以 $i$ 为根的子树，即当前起点为 $i$，$i$ 的子节点都逃走了，能抓到的最多晶蝶数量。

• $dp[i][1]$ 表示以 $i$ 为根的子树，即当前起点为 $i$，$i$ 的子节点都还在，能抓到的最多晶蝶数量。

状态转移：

当前节点：$cur$，当前节点的儿子节点：$nxt$。

我们对于上文提到的两种情况分别考虑：

1. 不返回 $cur$：只能选一个儿子节点去。

   • 因为到了 $cur$ 后，$cur$ 的所有孙子节点不受影响，可以随时去抓，不用考虑，到时候再回来抓就行了。所以 $dp[cur][0]$ 和 $dp[cur][1]$ 都应该加上所有 $dp[nxt][1]$ 的和 $sum$（即 $cur$ 的儿子跑了，孙子却能抓）。

   • $dp[cur][1]$：$cur$ 的儿子节点会跑，显然选择晶蝶数量最大的儿子节点去。

   • dp[cur][1] = sum + maxi_nxt; // 此处 maxi_nxt 是最大的 val[nxt]

   • $dp[cur][0]$：$cur$ 的儿子节点跑路了，但孙子节点都还能随便去，就是 $sum$。

   • dp[cur][0] = sum;

2. 返回 $cur$：如果子节点 $nxt$ 的 $t_{nxt} = 3$，可以通过返回过去。

   • 过程：首先走到了 $i$，然后返回 $cur$，最后去点 $j$。

   • 首先，我们确定要返回的点 $j$，肯定选 $cur$ 满足 $t_{nxt} = 3$ 的晶蝶数最大的子节点。可以想象成去掉以 $i$ 为根的子树后（因为要返回），选择最优的一个点去，与上文 $dp[cur][1]$ 不返回 $cur$ 的更新策略一样。

   • 前方连珠炮！！！

   • 枚举所有 $i$，对与每个 $i$，如果选择返回到其他节点，能抓到最大晶蝶数量 $tmpans$ 为：

   • 首先到达 $i$，$tmpans = tmpans + val[i]$。

   • $cur$ 的孙子都不会被影响，以后可以随便去抓，$tmpans = tmpans + sum$。

   • 但是 $i$ 的子节点会跑，所以 $tmpans = tmpans - dp[i][1]$。

   • 但是但是 $i$ 的子节点跑了，$i$ 的孙子节点还能去（逐渐离谱），此时 $dp[i][0]$ 终于派上用场，$tmpans = tmpans + dp[i][0]$。

   • OK，现在返回 $cur$，无事发生。

   • 最后到达 $j$，$tmpans = tmpans + val[j]$。

   • 但是但是但是，有可能 $i = j$，所以为了应对这种情况，还要维护一个备选的 $j$，即 $cur$ 满足 $t_{nxt} = 3$ 的晶蝶数次大的子节 $j2$。如果出现这种情况，则返回 $j2$ 而不是 $j$。

   • 但是但是但是但是，有可能 $j2$ 不存在，那就不返回了！到了 $cur$ 之后啥也不干了。（这样走好像没屁用，但是我们强制必须返回，所以就当凑数了~）

   • 对于每个 $tmpans$，取最大的，并尝试更新 $dp[cur][1]$，如果情况二更优，则用情况二。

真是一点都不恶心呢 ○( ＾芬芳＾)っ

代码：

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

const int N = 1e5 + 5;
int n, T, dp[N][2], val[N], t[N];
vector<int> nbr[N], g[N]; 

void dfs(int cur, int fa)
{
	dp[cur][0] = dp[cur][1] = 0;
	
	int sum = 0, maxi_nxt = 0;
	// 注意 maxi_nxt 设为 0，否则如果 cur 是叶子节点就凉了 
	
	for(auto nxt : nbr[cur])
	{
		if(nxt == fa)
			continue;
		dfs(nxt, cur);
		
		// 最大的子节点 
		maxi_nxt = max(maxi_nxt, val[nxt]);
		
		// cur 的子节点的晶蝶都逃走了，但 cur 的孙子节点可以随时去取，对应 dp[nxt][1] 
		sum += dp[nxt][1];
	}
	dp[cur][0] = sum;
	dp[cur][1] = sum + maxi_nxt; // 所有孙子可以随便取，但儿子只能选一条路 
	
	if(g[cur].size() == 0) // 没有 t = 3 的儿子，可以结束 
		return ; 
		
	// 有 t = 3 的儿子，还有别的方法
	
	int max1 = -2e18, max2 = -2e18, maxi = -2e18;
	// 最大值、次大值、情况二最优解 
	int max1id = 0, max2id = 0;
	// 最大值下标、次大值下标 
	
	for(auto nxt : g[cur]) // 计算 max1 和 max2 
	{
		if(nxt == fa)
			continue;
		if(val[nxt] > max1)
		{
			max2 = max1;
			max2id = max1id; // 传给次大值 
			max1 = val[nxt];
			max1id = nxt;
		}
		else if(val[nxt] > max2)
		{
			max2 = val[nxt];
			max2id = nxt;
		}
	}
	for(auto nxt : nbr[cur]) // 枚举返回前去的点 
	{
		if(nxt == fa)
			continue;
		if(nxt == max1id) // 要返回的儿子刚好是最大的 t = 3 的子节点，只能去次大点 
		{
			if(max2id == 0) // 没有次大点，不走了 
				maxi = max(maxi, val[nxt] + sum - dp[nxt][1] + dp[nxt][0]);
			else            // 有次大点 
				maxi = max(maxi, val[nxt] + sum - dp[nxt][1] + dp[nxt][0] + max2); 
		}
		else // 返回去最大的儿子 
			maxi = max(maxi, val[nxt] + sum - dp[nxt][1] + dp[nxt][0] + max1);
	}
	dp[cur][1] = max(maxi, dp[cur][1]); // 第二种情况：返回 
	return ;
}

void work()
{
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> val[i];
	for(int i = 1; i <= n; i++)
	{
		cin >> t[i];
		nbr[i].clear(); // 顺便把两个 vector 清空 
		g[i].clear();
	}
	for(int i = 1; i <= n - 1; i++)
	{
		int x, y;
		cin >> x >> y;
		
		// 记录能返回的点 
		if(t[x] == 3) g[y].push_back(x);
		if(t[y] == 3) g[x].push_back(y); 
		
		nbr[x].push_back(y);
		nbr[y].push_back(x);
	}
	dfs(1, 0);
	cout << dp[1][1] + val[1] << "\n"; // 注意 dp[1][1] 并不包含 val[1] 
	return ;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> T;
	while(T--)
		work();
	return 0;
}
// 码量感人 QWQ