Google Code Jam 2022-QR-T4-Chain Reactions
Primo Pan
  2022-04-03 22:17:16 2022-04-03 22:17    

题面

Problem Wile lives alone in the desert, so he entertains himself by building complicated machines that run on chain reactions. Each machine consists of N modules indexed 1,2,…,N. Each module may point at one other module with a lower index. If not, it points at the abyss.

Modules that are not pointed at by any others are called initiators. Wile can manually trigger initiators. When a module is triggered, it triggers the module it is pointing at (if any) which in turn may trigger a third module (if it points at one), and so on, until the chain would hit the abyss or an already triggered module. This is called a chain reaction.

Each of the N modules has a fun factor Fi. The fun Wile gets from a chain reaction is the largest fun factor of all modules that triggered in that chain reaction. Wile is going to trigger each initiator module once, in some order. The overall fun Wile gets from the session is the sum of the fun he gets from each chain reaction.

For example, suppose Wile has 4 modules with fun factors F1=60,F2=20,F3=40, and F4=50 and module 1 points at the abyss, modules 2 and 3 at module 1, and module 4 at module 2. There are two initiators (3 and 4) that Wile must trigger, in some order.

Example in statement when activating 4 then 3.

As seen above, if Wile manually triggers module 4 first, modules 4, 2, and 1 will get triggered in the same chain reaction, for a fun of max(50,20,60)=60. Then, when Wile triggers module 3, module 3 will get triggered alone (module 1 cannot get triggered again), for a fun of 40, and an overall fun for the session of 60+40=100.

Example in statement when activating 3 then 4.

However, if Wile manually triggers module 3 first, modules 3 and 1 will get triggered in the same chain reaction, for a fun of max(40,60)=60. Then, when Wile triggers module 4, modules 4 and 2 will get triggered in the same chain reaction, for a fun of max(50,20)=50, and an overall fun for the session of 60+50=110.

Given the fun factors and the setup of the modules, compute the maximum fun Wile can get if he triggers the initiators in the best possible order.

Input
The first line of the input gives the number of test cases, T. T test cases follow, each described using 3 lines. Each test case starts with a line with a single integer N, the number of modules Wile has. The second line contains N integers F1,F2,…,FN where Fi is the fun factor of the i-th module. The third line contains N integers P1,P2,…PN. If Pi=0, that means module i points at the abyss. Otherwise, module i points at module Pi.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum fun Wile can have by manually triggering the initiators in the best possible order.

Limits
Memory limit: 1 GB.
1≤T≤100.
1≤Fi≤109.
0≤Pi≤i−1, for all i.
Test Set 1 (Visible Verdict)
Time limit: 5 seconds.
1≤N≤10.
Test Set 2 (Visible Verdict)
Time limit: 5 seconds.
1≤N≤1000.
Test Set 3 (Hidden Verdict)
Time limit: 10 seconds.
1≤N≤100000.
Sample
Sample Input
save_alt
content_copy
3
4
60 20 40 50
0 1 1 2
5
3 2 1 4 5
0 1 1 1 0
8
100 100 100 90 80 100 90 100
0 1 2 1 2 3 1 3
Sample Output
save_alt
content_copy
Case #1: 110
Case #2: 14
Case #3: 490
Sample Case #1 is the one explained in the problem statement.

In Sample Case #2, there are 4 initiators (modules 2 through 5), so there are 4 chain reactions. Activating them in order 3,5,4,2 yields chains of fun 3,5,4,2 for an overall fun of 14. Notice that we are summing the four highest fun numbers in the input, so there is no way to get more than that.

In Sample Case #3, an optimal activation order of the 5 initiators is 4,5,7,6,8.

题目大意

给你一大坨点带权的森林。对于每棵树，每一次选择一个叶子结点一路走到根，对答案的贡献是这条路径上的最大值，并且走完之后路径上的点权就废了。可以知道改变选择叶子结点的顺序会得到不同的答案。现在求整个森林得到的最大答案是啥。

思路

写完三题过关就没看后面的，这两天补一下。

森林里每棵树是独立的。分治一下，如果是一个孤立的点，答案就是本身的权值。如果只有一个儿子，记一个结点的答案是f(i)，那么对于父亲u，答案就是max{val[u],f(i)}。

当有多个儿子的时候，其实就按照题面那个动态图的意思搞就行（谷歌用户体验牛逼，吹一把，题面都会动，太良心了）。其实这个时候就是针对所有儿子，选中的第一个就会把当前结点的值跑掉。我们已经dfs完了所有儿子，可以意会到，贪心地选择最小的一个答案，把它和val[u]比一下大小。如果比val[u]来得大，那么val[u]肯定对答案没有贡献。如果比val[u]小，那么相当于val[u]顶替掉最小的那份答案，而其他比之大的答案都应该直接贡献到最后的ans里。 

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll N=100005;

ll vis[N],val[N];
vector<ll> G[N];
ll n,ans,f;

ll dfs(ll u,ll fa)
{
    vis[u]=1;
    vector<ll> dp;
    ll sz=G[u].size();
    for (ll i=0;i<sz;i++)
    {
        ll v=G[u][i];
        ll p=dfs(v,u);
        dp.push_back(p);
    }
    sort(dp.begin(),dp.end());
    if (sz==0)
        return val[u];
    for (ll i=1;i<sz;i++)
        ans+=dp[i];
    return max(dp[0],val[u]);
}
int main()
{
    ll T;
    cin>>T;
    for (ll t=1;t<=T;t++)
    {
        cin>>n;
        for (ll i=1;i<=n;i++)
            cin>>val[i];
        for (ll i=1;i<=n;i++)
            G[i].clear();
        for (ll i=1;i<=n;i++)

        {
            ll fa;
            cin>>fa;
            G[fa].push_back(i);
        }

        f=ans=0;
        memset(vis,0,sizeof(vis));
        for (ll i=1;i<=n;i++)
        {
            if (!vis[i])
                f+=dfs(i,-1);
        }
        ans=ans+f;
        cout<<"Case #"<<t<<": ";
        cout<<ans<<endl;
    }
}