题解：P9847 [ICPC2021 Nanjing R] Crystalfly

Stone_Xz · 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 状态：

状态转移：

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

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

不返回 cur：只能选一个儿子节点去。
- 因为到了 cur 后，cur 的所有孙子节点不受影响，可以随时去抓，不用考虑，到时候再回来抓就行了。所以 dp[cur][0] 和 dp[cur][1] 都应该加上所有 dp[nxt][1] 的和 sum（即 cur 的儿子跑了，孙子却能抓）。
- - ```dp[cur][1] = sum + maxi_nxt; // 此处 maxi_nxt 是最大的 val[nxt]```
- dp[cur][0] = sum;
返回 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]。
- 但是 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