Htto的小站
0%

Crystalfly

发表于 更新于 分类于 ，

H-Crystalfly

题目大意

给你一颗树，每个节点都有两个值，一个是权值\(a_i\)，还有一个是失效时间\(t_i\)。你一开始在1号节点，如果你在\(t\)时刻走到一个一个点，那么他的所有相邻的点的权值将会在\(t+t_i\)秒末清零。每走到一个点将会采集这个点的权值，问你最多能采集多少权值

解题思路

到达一个节点后，子节点就会立即计时，我们发现\(t_i\)的范围是\(1...3\)我们逐一来考虑\(t_i\)的情况。 * \(t_i=1\)，那么如果走到父节点后不立即走到他的话，他的权值就会立即变为0 * \(t_i=2\)，可以发现这种情况和\(t_i=1\)等价，因为你从一个兄弟走到这个节点一定来不及。 * \(t_i=3\)，从父节点出动，如果你第一秒走到一个兄弟节点，第二秒回头，那么第三秒你还来得及回头来获得这个节点的权值。

我们发现节点可能会返回，但是一旦\(u\)返回到他的父节点，那么他的孩子们将会挂掉。我们dp开三维 \(f[u][t][0/1]\),你在\(t\)时刻访问了\(u\)节点，这个时刻是你从访问父节点时刻到当前时刻的差值，最大为4（因为4以上都没什么意义）。 那么我们开始考虑转移。首先我们考虑需要返回的情况，那么孩子们都会挂掉 \(f(u,t,1)= a_u[t\le t_u]+\sum\limits_{v\in sons(u)}{f(v,4,0)}\) 现在我们开始转移不需要返回的状态。分类讨论，容易知道，我们最多保住两个孩子，但是有的时候只保一个会比较优

  1. 如果我们只保留一个孩子，我们就找到一个孩子权值最大的加上去就行。\(f(u,t,0)\leftarrow f(u,t,1)+max(a_v)\)
  2. 如果要保留两个孩子，情况会稍微复杂一点，我们第一步可以先挑一个点走，然后返回父节点，第三步走到一个\(t=3\)的节点上。\(f(u,t,0)\leftarrow \max\limits_{v_1,v_2\in son(u)}{(a_u[t\le t_u]+f(u,1,1)+f(v_1,1,1)-f(v_1,4,0)+f(v_2,3,0))}\)其中\(T_{v_2}=3\),我们用一个multiset维护。见代码

ps: 第二维发现只有两个情况，选和不选

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <set>

#define int long long
using namespace std;
const int maxn = 1e5 + 5;
vector<int> A;
vector<int> T;
vector<vector<int>> G;
int n;

int dp[maxn][5][2];
int dfs(int u, int p, int t, bool back)
{
    int &ans = dp[u][t][back];
    if (dp[u][t][back] != -1)
        return ans;

    ans = 0;
    if (t <= T[u])
        ans += A[u];
    // 记录t=3孩子的权值
    multiset<int> tab;
    //[子节点权重,子节点编号]
    vector<pair<int, int>> ch;

    int base = ans;
    // 孩子全部死翘翘的情况
    for (auto v : G[u])
    {
        if (v == p)
            continue;
        ch.push_back({A[v], v});

        if (T[v] == 3)
            tab.insert(A[v]);
        base += dfs(v, u, 4, false);
    }
    // 如果这个节点要返回的话，那么我们所有孩子都会挂掉，我们直接返回。
    if (back)
        return ans = base;
    // 权值最大的孩子，如果我们不保留两个节点，我们就取权值最大的孩子
    sort(ch.begin(), ch.end());

    // 叶子节点
    if (ch.empty())
        return ans = base;

    // 保一个孩子
    ans = base + ch.back().first;
    // 没有t=3孩子，那么最多保一个
    tab.insert(-0x3f3f3f3f3f);
    for (auto [w, v] : ch)
    {
        if (T[v] == 3)
            tab.erase(tab.find(A[v]));
        ans = max(ans, base + dfs(v, u, 1, true) - dfs(v, u, 4, false) + *tab.rbegin());
        if (T[v] == 3)
            tab.insert(A[v]);
    }
    return ans;
}

### AC代码
void solve()
{

    A.clear(), T.clear(), G.clear();
    cin >> n;
    A.resize(n + 1), T.resize(n + 1), G.resize(n + 5);

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= 4; j++)
            dp[i][j][0] = dp[i][j][1] = -1;

    for (int i = 1; i <= n; i++)
        cin >> A[i];
    for (int i = 1; i <= n; i++)
        cin >> T[i];
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    cout << dfs(1, 1, 1, false) << "\n";
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    try
    {
        int T;
        cin >> T;
        while (T--)
            solve();
    }
    catch (exception &e)
    {
        cout << e.what();
    }
    return 0;
}