2021 ICPC 南京 H-Crystalfly(树上DP)2021 ICPC 南京 H-Crystalfly(树上DP)

68 阅读 0 评论 45 点赞

我是靠谱客的博主欣慰御姐，最近开发中收集的这篇文章主要介绍2021 ICPC 南京 H-Crystalfly(树上DP)2021 ICPC 南京 H-Crystalfly(树上DP)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

2021 ICPC 南京 H-Crystalfly(树上DP)

Probelm Statement

你一开始处于 $1$ 号节点的树, 每个点 $a_i$ 个蝴蝶, 且如果 $i^{th}$ 节点的父节点被扰动时, 这些蝴蝶会在 $t_i(1leq t_ileq 3)$ 时刻后消散. 求你可以抓到多少只蝴蝶.

Solution

当我们第一次到达节点 $u$ 的时候它的所有儿子都会被激活，对于 $u$ 的子节点 $v$ ，我们只有两个决策，要么到达子节点 $v$ 知乎继续向下，那么 $u$ 的其他子节点上的蝴蝶都无法再次抓取. 或者我们进入某个子节点 $v_1(t_{v_1}=3)$ 后立刻返回节点 $u$ 挑另一个子节点 $v_2$ 直接走下去, 然后除了 $v_1,v_2$ 以外 $u$ 的其他子节点上的蝴蝶都会消失.

我们不妨设:

$f_i$ : 我们取节点 $i$ , 可以取 $i$ 子节点上的蝴蝶可以收获的最大蝴蝶数.
$g_i$ : 我们不取节点 $i$ 上的蝴蝶, 可取 $i$ 子节点上的蝴蝶的最大蝴蝶数.
$h_i$ : 我们节点 $i$ 上的蝴蝶, 但是不取 $i$ 子节点上的蝴蝶可以收获的最大蝴蝶数.

对于 $h_u$ 根据上述定义我们可以得到, $h_u=sumlimits_{vintext{son}u}g_v+a_u$ .

由于 $f_u$ 和 $g_u$ 的区别主要在于节点 $u$ 上的蝴蝶去不去得到, 我们有 $f_u=g_u+a_u$ .

接下来我们考虑计算 $g_u$ 根据上述两种两种决策:

请添加图片描述

Code

# define Fast_IO std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
# include "unordered_map"
# include "algorithm"
# include "iostream"
# include "cstdlib"
# include "cstring"
# include "cstdio"
# include "vector"
# include "bitset"
# include "queue"
# include "cmath"
# include "map"
# include "set"
 
using namespace std;
 
const int maxm=1e5+10;
 
int Task,N;
long long A[maxm];
int T[maxm];
long long F[maxm],G[maxm],H[maxm];

vector<int> Edge[maxm];
 
void Dfs(int Now,int Father){
	long long Max1,Max2,Max; Max=Max1=Max2=0;
	long long Res=0;
	for(auto To:Edge[Now]){
		if(To==Father) continue;
		Dfs(To,Now);
	}H[Now]=A[Now];
	for(auto To:Edge[Now]){
		if(To==Father) continue;
		H[Now]+=G[To];
	}
	for(auto To:Edge[Now]){
		if(To==Father) continue;
		Res+=G[To];
		Max=max(A[To],Max);
	}G[Now]=Res+Max;
	Max1=Max2=0;
	for(auto To:Edge[Now]){
		if(To==Father || T[To]!=3) continue;
		if(A[To]>=Max1) Max2=Max1,Max1=A[To];
		else Max2=max(Max2,A[To]);
	}
	for(auto To:Edge[Now]){
		if(To==Father) continue;
		if(A[To]!=Max1 || T[To]!=3) G[Now]=max(G[Now],Res-G[To]+H[To]+Max1);
		else G[Now]=max(G[Now],Res-G[To]+H[To]+Max2);
	}
	F[Now]=G[Now]+A[Now];
	return;
}
 
inline void Solve(){
	static int i,U,V;
	scanf("%d",&N);
	for(i=1;i<=N;i++) Edge[i].clear(),F[i]=G[i]=false;
	for(i=1;i<=N;i++) scanf("%lld",&A[i]);
	for(i=1;i<=N;i++) scanf("%d",&T[i]);
	for(i=1;i< N;i++){
		scanf("%d%d",&U,&V);
		Edge[U].push_back(V);
		Edge[V].push_back(U);
	}Dfs(1,1);
	printf("%lldn",F[1]);
	return;
}
 
int main(){
	scanf("%d",&Task);
	while(Task--) Solve();
	return 0;
}