工作沟通
时间限制：1.0 s
内存限制：128.0 MB
问题描述
某公司有N名员工，编号从0至N-1。其中，除了0号员工是老板，其余每名员工都有一个直接领导。我们假设编号为i的员工的直接领导是fi。
该公司有严格的管理制度，每位员工只能受到本人或本人直接领导或间接领导的管理。具体来说，规定员工x可以管理员工y，当且仅当x=y，或f=fy，或x可以管理fy。特别地，0号员工老板只能自我管理，无法由其他任何员工管理。
现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？
输入描述
第一行一个整数N，表示员工的数量。
第二行N-1个用空格隔开的正整数，依次为f1,f2…,fN-1。
第三行一个整数Q，表示共有Q场合作需要安排。
接下来Q行，每行描述一场合作：开头是一个整数m（2≤m≤N），表示参与本次合作的员工数量；接着是m个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。
保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。
输出描述
输出Q行，每行一个整数，依次为每场合作的主持人选。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4
样例输出 1
2 2 0
样例解释 1
对于第一场合作，员工3,4有共同领导2，可以主持合作。
对于第二场合作，员工2本人即可以管理所有参与者。
对于第三场合作，只有0号老板才能管理所有员工。
样例输入 2
7 0 1 0 2 1 2 5 2 4 6 2 4 5 3 4 5 6 4 2 4 5 6 2 3 4
样例输出 2
2 1 1 1 0
数据规模
对于50%的测试点，保证N≤50。
对于所有测试点，保证3≤N≤300；Q≤100 。
相似题推荐
执行如下代码，会输出 钢琴：叮咚叮咚 和 吉他：咚咚当当 。这体现了面向对象编程的（ ）特性。
class Instrument {
public:
virtual void play() {
cout << "乐器在演奏声音" << endl;
}
virtual ~Instrument() {}
};
class Piano : public Instrument {
public:
void play() override {
cout << "钢琴：叮咚叮咚" << endl;
}
};
class Guitar : public Instrument {
public:
void play() override {
cout << "吉他：咚咚当当" << endl;
}
};
int main() {
Instrument* instruments[2];
instruments[0] = new Piano();
instruments[1] = new Guitar();
for (int i = 0; i < 2; ++i) {
instruments[i]->play();
}
for (int i = 0; i < 2; ++i) {
delete instruments[i];
}
return 0;
} | A． 继承 |
B． 封装 |
| C． 多态 |
D． 链接 |
在二叉排序树（Binary Search Tree, BST）中，假设节点值互不相同。给定如下搜索函数，以下说法一定正确的是（ ）。
bool find(Node* root, int x) {
while (root) {
if (root->val == x) return true;
root = (x < root->val) ? root->left : root->right;
}
return false;
} | A． 最坏情况下，访问结点数是O(logn) |
B． 最坏情况下，访问结点数是O(n) |
| C． 无论如何，访问结点数都不超过树高的一半 |
D． 一定比在普通二叉树中搜索快 |
0/1 背包（每件物品最多选一次）问题通常可用一维动态规划求解，核心代码如下。则下面说法正确的是（）。
for each item (w, v): for (int j = W; j >= w; --j) dp[j] = max(dp[j], dp[j-w] + v);
| A． 内层 j 必须从小到大，否则会漏解 |
B． 内层 j 必须从大到小，否则同一件物品会被用多次 |
| C． j 从大到小或从小到大都一样 |
D． 只要 dp 初始为 0 ，方向无所谓 |
下面代码实现了哈夫曼编码，则横线处应填写的代码是（ ）。
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct Symbol {
char ch; //字符
long long freq; //频率
string code; //哈夫曼编码
};
struct Node {
long long w; //权值
int l, r; //左右孩子（节点下标），-1 表示空
int sym; //叶子对应符号下标；内部节点为 -1
Node(long long _w = 0, int _l = -1, int _r = -1, int _sym = -1)
: w(_w), l(_l), r(_r), sym(_sym) {}
};
// 从 A(leafIdx) 和 B(internalIdx) 的队首取最小的一个节点下标
static int PopMinNode(const vector<Node>& nodes,
const vector<int>& leafIdx, int n, int& pA,
const vector<int>& internalIdx, int& pB)
{
if (pA < n && (pB >= (int)internalIdx.size() ||
nodes[leafIdx[pA]].w <= nodes[internalIdx[pB]].w))
{
return leafIdx[pA++];
}
else
{
return internalIdx[pB++];
}
}
// DFS 生成编码（左 0，右 1）
static void DFSBuildCodes(int u, const vector<Node>& nodes, Symbol sym[], string& path)
{
if (u == -1)
return;
if (nodes[u].sym != -1) // 叶子
{
sym[nodes[u].sym].code = path;
return;
}
path.push_back('0');
DFSBuildCodes(nodes[u].l, nodes, sym, path);
path.pop_back();
path.push_back('1');
DFSBuildCodes(nodes[u].r, nodes, sym, path);
path.pop_back();
}
int BuildHuffmanCodes(Symbol sym[], int n)
{
for (int i = 0; i < n; i++)
sym[i].code.clear();
if (n <= 0)
return -1;
// 只有一个字符：约定编码为 "0"
if (n == 1)
{
sym[0].code = "0";
return 0;
}
vector<Node> nodes;
nodes.reserve(2 * n);
// 1) 建立叶子节点
vector<int> leafIdx(n);
for (int i = 0; i < n; i++)
{
leafIdx[i] = (int)nodes.size();
nodes.push_back(Node(sym[i].freq, -1, -1, i));
}
// 2) 叶子按权值排序（A 队列）
sort(leafIdx.begin(), leafIdx.end(),
[&](int a, int b)
{
if (nodes[a].w != nodes[b].w)
return nodes[a].w < nodes[b].w;
return nodes[a].sym < nodes[b].sym; // 稳定一下
});
// B 队列（内部节点下标队列）
vector<int> internalIdx;
internalIdx.reserve(n);
int pA = 0, pB = 0;
// 3) 合并 n-1 次
for (int k = 1; k < n; k++)
{
int x = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
int y = PopMinNode(nodes, leafIdx, n, pA, internalIdx, pB);
int z = (int)nodes.size();
// =====================在此处填写代码=====================
}
int root = internalIdx.back();
// 4) DFS 生成编码
string path;
DFSBuildCodes(root, nodes, sym, path);
return root;
} A．nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); internalIdx.push_back(z); |
B．nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, -1)); leafIdx.push_back(z); |
C．internalIdx.push_back(z); nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); |
D．nodes.push_back(Node(nodes[x].w + nodes[y].w, x, y, x+y)); leafIdx.push_back(z); |
关于以下代码，说法正确的是（ ）。
class Instrument {
public:
void play() {
cout << "乐器在演奏声音" << endl;
}
virtual ~Instrument() {}
};
class Piano : public Instrument {
public:
void play() override {
cout << "钢琴：叮咚叮咚" << endl;
}
};
class Guitar : public Instrument {
public:
void play() override {
cout << "吉他：咚咚当当" << endl;
}
};
int main() {
Instrument* instruments[2];
instruments[0] = new Piano();
instruments[1] = new Guitar();
for (int i = 0; i < 2; ++i) {
instruments[i]->play();
}
for (int i = 0; i < 2; ++i) {
delete instruments[i];
}
return 0;
} | A． 执行代码会输出两行，内容分别为： 钢琴：叮咚叮咚 和 吉他：咚咚当当 |
B． 执行代码会输出两行，内容分别为： 乐器在演奏声音 和 乐器在演奏声音 |
| C． 代码编译出现错误 |
D． 代码运行出现错误 |
