在一个特定的公司里,有一个树根形式的层级。集团管理层包括n人员: 首席执行官(领导者,树根)掌握着数字1; 剩下的每一个n−1会员有自己的直接主管:会员号主管i有号码pi; 此外,该i-第一次n经理拥有ai直接隶属关系中的普通“下属”(不同管理者下属的集合不相交)。 你需要传递一个重要的信息,让尽可能多的人知道。众所周知,一个人一旦收到消息,就会把它传递给所有的直接下属。普通下属会立即收到经理发来的信息,以及经理的号码i从他们的主管那里收到消息ti分钟。 你正好有T分钟,只需拨打一次电话n经理。选择打电话给谁,以便联系到尽可能多的人T分钟。 投入 第一行包含两个整数n和T—管理人员的数量和传播消息的时限(1≤n≤105; 0≤T≤109). 下一行包含n−1整数p2,…,pn—经理的直接主管人数2到n (1≤pi≤n).保证层次结构是以节点为根的树1. 第三行包含n−1整数t2,…,tn—消息从其直接主管到达相应经理所用的时间(0≤ti≤109). 最后一行包含n整数ai同格式—每位经理的普通下属人数(0≤ai≤109). 输出 打印两个用空格分隔的整数:您呼叫的经理的电话号码,以及将在内收到消息的总人数T分钟。 如果有多个最佳答案,打印其中任何一个。
时间: 2024-04-17 18:25:21 浏览: 92
根据题目描述,我们需要选择一个经理,使得在给定的时间限制内,尽可能多的人收到消息。我们可以通过动态规划来解决这个问题。
首先,我们定义一个二维数组`dp`,其中`dp[i][j]`表示在给定时间`j`内,以节点`i`为根的子树中能够传递消息的最大人数。
然后,我们可以使用递归的方式来填充`dp`数组。假设节点`i`有`k`个直接下属,那么可以将问题分解为以下子问题:
- 当前节点`i`收到消息的时间为`t[i]`,那么在给定时间`j`内,节点`i`能够传递消息的最大人数为`min(a[i], j - t[i])`,其中`a[i]`表示节点`i`的普通下属人数。
- 对于节点`i`的每个直接下属节点`child`,我们可以递归计算以节点`child`为根的子树中能够传递消息的最大人数,并将结果累加到节点`i`的最大人数中。
最后,我们可以通过遍历所有经理节点,找到在给定时间限制内能够传递消息的最大人数,并记录对应的经理电话号码。
下面是一个使用C++编写的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<int> p; // 直接主管人数
vector<int> t; // 消息到达时间
vector<int> a; // 普通下属人数
vector<vector<int>> dp; // 动态规划数组
// 填充dp数组
void fillDP(int node, int T) {
dp[node][0] = 0;
int maxTime = T - t[node];
for (int i = 1; i <= maxTime; i++) {
dp[node][i] = a[node];
}
for (int child : p[node]) {
fillDP(child, T);
for (int i = maxTime; i >= 1; i--) {
dp[node][i] = max(dp[node][i], dp[child][i - 1] + a[node]);
}
}
}
int main() {
int n, T;
cin >> n >> T;
p.resize(n + 1);
t.resize(n + 1);
a.resize(n + 1);
dp.resize(n + 1, vector<int>(T + 1, 0));
for (int i = 2; i <= n; i++) {
cin >> p[i];
}
for (int i = 2; i <= n; i++) {
cin >> t[i];
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
fillDP(1, T);
int maxPeople = 0;
int manager = 1;
for (int i = 1; i <= n; i++) {
if (dp[i][T] > maxPeople) {
maxPeople = dp[i][T];
manager = i;
}
}
cout << manager << " " << maxPeople << endl;
return 0;
}
```
在上述示例中,我们通过读取输入构建了输入数据,并使用`fillDP`函数填充了`dp`数组。最后,我们遍历所有经理节点,找到在给定时间限制内能够传递消息的最大人数,并输出对应的经理电话号码。
请注意,这只是一个示例代码,实际使用时,你可能需要根据具体情况进行适当修改。
阅读全文