The 2021 ICPC Asia Nanjing Regional Contest H. Crystalfly

The 2021 ICPC Asia Nanjing Regional Contest H. Crystalfly

H. Crystalfly

题意

给定一棵$n$个节点的树，每个节点有$a[i]$个蝴蝶，如果蝴蝶被惊动了会在$t[i]$时间后飞走，被惊动的条件是你走到该节点相邻的节点。最开始$0$时刻你在$1$号节点，走一条边需要时间为$1$,你有无限时间抓蝴蝶，问最多能抓到多少蝴蝶。
$1<=n<=10^5$ $1<=ai<=10^9$ $1<=ti<=3$

思路

首先可以从题目中得到，当到达一个节点时，该节点的子节点上的蝴蝶全都会被惊动，而从一个子节点走到另一个子节点花费的时间为$3$。所以当选择抓一个子节点的蝴蝶后，还可以选择一个时间$t[i]=3$的子节点抓蝴蝶，其他子节点的蝴蝶都会飞走。

给出$DP$方程定义：
$f[u][1][1]$:该点的蝴蝶抓，且该点的子节点至少抓一个
$f[u][1][0]$:该点的蝴蝶抓，但该点的子节点一个都不抓
$f[u][0][1]$:该点的蝴蝶不抓，但该点的子节点的至少抓一个节点的蝴蝶
现在考虑：
对于父节点$u$的子节点$vi$ ,我们至少可以选择一个节点得到$a[v]$的蝴蝶。其他的子节点$vi$的子节点一定至少可以有一个可以抓到蝴蝶。
若$t[vi]=3$ 则可以到其他分支$vj$上再取一点再跑回该节点$vi$来， 但是取的另一个节点$vj$的子节点的蝴蝶一定抓不到了。
所以我们对于每个节点$u$的子节点有两种取法
设一个节点有$m$个子节点
$1$.抓一个子节点舍弃其他点的蝴蝶 $f[vi][1][1]+{\sum }_{k=1}^{m}f[vk][0][1](i!=k)$
$2$.当我们选择抓的蝴蝶时间为$t[vi]=3$ 我们可以再抓一个点的蝴蝶 $f[vi][1][1]+f[vj][1][0]+{\sum }_{k=1}^{m}f[vk][0][1](i!=j!=k)$
我们可以枚举要抓的蝴蝶$vi$,对于是否要再抓一次蝴蝶取最大值即可

代码

#include 
#include 
#include 
using namespace std;
#define ll long long
const int N = 1e5 + 10;
typedef pair<int,int>PII;
int a[N],t[N],n;
vector<int>g[N];
ll f[N][2][2];
/*
f[u][1][1]:该点的值取，且该点子节点的至少取一个
f[u][1][0]:该点的值取，但该点子节点的值不取
f[u][0][1]:该点的值不取，该点子节点的至少取一个
*/
struct node
{
    int id;//节点编号
    ll res;//值
    bool operator < (const node &A)const{
        return res > A.res;
    }
};

void dfs(int u,int fa)
{
	f[u][0][1] = 0;
    f[u][1][1] = f[u][1][0] = a[u];//初始化
    vector<node>tmp;
    ll sum = 0,ans = 0;

	//先全部取第一种情况 即只抓一个节点的蝴蝶，其余节点的蝴蝶舍去
    for(int v : g[u])
    {
        if(v == fa) continue ;
        dfs(v, u);   
        sum += f[v][0][1];//记录下所有子节点都可以取子节点的和
        tmp.push_back({v, f[v][1][0] - f[v][0][1]});//第二种情况，选一个节点v先取，再去最后要取的节点
    }

    sort(tmp.begin(), tmp.end());
    int siz = tmp.size();
    for(int v : g[u])//枚举一定取的节点即f[v][1][1],对于两种情况取最大值
    {
        if(v == fa) continue ;
        ans = max(ans, sum + f[v][1][1] - f[v][0][1]);
        if(t[v] == 3)
        {
			//注意第二种情况抓的两个子节点的蝴蝶，节点编号不能重叠
            if(tmp[0].id != v) ans = max(ans, sum + f[v][1][1] - f[v][0][1] + tmp[0].res);
            else if(siz >= 2) ans = max(ans, sum + f[v][1][1] - f[v][0][1] + tmp[1].res);
        }
    }
    f[u][1][1] += ans;
    f[u][0][1] += ans;
    f[u][1][0] += sum;
    return ;
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++){
        scanf("%d",&a[i]);
    }
    for(int i = 1; i <= n; i ++){
        scanf("%d",&t[i]);
        g[i].clear();
    }
    for(int i = 1; i < n; i ++){
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    printf("%lld\n",f[1][1][1]);
    return ;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T --) solve();
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87