https://codeforces.ml/contest/1746/problem/D
题目大意：一棵n节点有根树，根节点为1，分别有两个数组
s[i] 顶点 i 的魅力值
c[i] 覆盖顶点 i 的路径数
每个顶点的路径数必须满足，同一父节点的子节点| c[v1]-c[v2] | <= 1
问当有k条路径时，∑c[i]*s[i]的最大值
思路：
因为同一父节点的子节点 | c[v1]-c[v2] | <= 1，所以对于父节点来说，每次都需要平分路径数，如果有多余的路径则考虑
分给贡献最大的前几个节点各一个
现在对于每个节点有两种状态，平分 or 多获取一个
f[i][2] 分别表示这两种状态，用优先队列实现选择贡献多的节点，同时加上记忆化搜索防止TLE
1 # include<iostream>
2 # include<bits/stdc++.h>
3 using namespace std;
4 # define int long long
5 # define endl "\n"
6 const int N = 2e5 + 10;
7 vector<int> g[N];
8 int s[N];
9 int c[N];
10 map<pair<int, int>, int> mp;
11 int f[N][2];
12 int d[N];
13 int dfs2(int u, int F) {
14 d[u] = g[u].size();
15 if(d[u] == 0) return F*s[u];
16 if (mp.count({u, F})) return mp[ {u, F}];//当前状态是否被搜索过
17 int f0 = F / d[u];//平分状态的路径数
18 int re = F % d[u];
19 int sum = F * s[u];
20 int f1 = (F + d[u] - 1) / d[u];//多获取状态的路径数
21 priority_queue<int> q;
22 for (auto v : g[u]) {
23 f[v][0] = dfs2(v, f0);
24 if (f0 == f1) f[v][1] = f[v][0];
25 else f[v][1] = dfs2(v, f1);
26 sum += f[v][0];
27 q.push(f[v][1] - f[v][0]);//优先队列保存的是多出来的路径所能产生的最大贡献
28 }
29 while (re--) {
30 sum += q.top();
31 q.pop();
32 }
33 return mp[ {u, F}] = sum;
34
35 }
36 void solve() {
37 int n, k;
38 cin >> n >> k;
39 mp.clear();
40 for (int i = 1; i <= n; ++i) {
41 g[i].clear();
42 f[i][1] = f[i][0] = 0;
43 }
44 for (int i = 2; i <= n; ++i) {
45 int x;
46 cin >> x;
47 g[x].push_back(i);
48 }
49 for (int i = 1; i <= n; ++i) cin >> s[i];
50 cout << dfs2(1, k) << endl;
51
52 }
53 int tt;
54 signed main() {
55 ios::sync_with_stdio(false);
56 cin.tie(0);
57 cout.tie(0);
58 tt = 1;
59
61 cin >> tt;
62 while (tt--)solve();
63
64
65 return 0;
66 }
