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

Probelm Statement

你一开始处于\(1\)号节点的树, 每个点\(a_i\)个蝴蝶, 且如果\(i^{th}\)节点的父节点被扰动时, 这些蝴蝶会在\(t_i(1\leq t_i\leq 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=\sum\limits_{v\in\text{son}u}g_v+a_u\).

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

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

第一种决策, 我们在节点\(u\)到达子节点\(v\)后一直往下, 节点\(u\)的其他子节点的蝴蝶都无法取到, 有转移方程式子: \(g_u=\max\{f_{v_1}+\sum\limits_{v_2\in\text{son}_u\and v_2\neq v_1}g_{v_2}\}=\sum\limits_{v\in\text{son}_u}g_v+\max\limits_{v\in\text{son}_v}\{a_v\}(v_1\in\text{son} _u)\).

第二种情况, 我们到达一个节点\(v_1\)后立刻返回, 然后选择一个节点\(v_2(t_{v_2}=3)\)一直往下, 其他子节点都无法取到, 我们有状态转移方程: \(g_u=\max\{f_{v_1}+h_{v_2}+\sum\limits_{v_3\in\text{son}_u\and v_3\neq v_2\and v_3\neq v_1}g_{v_3}\}=\max\{a_{v_1}+h_{v_2}+\sum\limits_{v_3\in\text{son}_u\and v_3\neq v_1\and v_3\neq v_2}g_{v_3}\}(v_1,v_2,v_3\in\text{son}_u,t_{v_1}=3)\). 对于情况\(2\)显然我们可以枚举\(v_1\)和\(v_2\)时间复杂度是\(O(n^2)\)的无法通过所有测试数据. 我们考虑维护\(a_{v_2}\)的最大值\(Max_1\)和次大值\(Max_2\), 然后扫一遍\(u\)的所有子节点\(v\). 如果\(t_{v}=3\and a_v=Max_1\)那么我们就计算\(g_u=max(g_u,h_v+\sum\limits_{v_1\in\text{son}_u\and v_1\neq v}g_{v_1}+Max_2)\)否则计算: \(g_u=max(g_u,h_v+\sum\limits_{v_1\in\text{son}_u\and v_1\neq v}g_{v_1}+Max_1)\). 由于\(\sum\limits_{v\in\text{son}_u}g_v\)可以\(O(\deg_u)\)预处理的, 所以上述转移式子在一个节点点\(u\)的复杂度为\(O(\deg_u)\).

上述算法的总复杂度为\(O(\sum_{i=1}^n\deg_i)=O(n)\).

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("%lld\n",F[1]);
	return;
}
 
int main(){
	scanf("%d",&Task);
	while(Task--) Solve();
	return 0;
} 

Orz dls

算法来源: Namomo Camp Day1.

Link

Codeforces Gym: The 2021 ICPC Asia Nanjing Regional Contest(XXII Open Cup,Grand Prix of Nanjing).

Vjudge: Namomo Spring Camp 2022 Div1 Week1 A.