題目描述

某公司有 $N$ 名員工，編號從 $0$ 至 $N?1$。其中，除了 $0$ 號員工是老板，其余每名員工都有一個直接領導。我們假設編號為 $i$ 的員工的直接領導是 $f_i$。

該公司有嚴格的管理制度，每位員工只能受到本人或直接領導或間接領導的管理。具體來說，規定員工 $x$ 可以管理員工 $y$，當且僅當 $x=y$，或 $x=f_y$，或 $x$ 可以管理 $f_y$。特別地，$0$ 號員工老板只能自我管理，無法由其他任何員工管理。

現在，有一些同事要開展合作，他們希望找到一位同事來主持這場合作，這位同事必須能夠管理參與合作的所有同事。如果有多名滿足這一條件的員工，他們希望找到編號最大的員工。你能幫幫他們嗎？

輸入格式

第一行一個整數 $N$ ，表示員工的數量。

第二行 $N?1$ 個用空格隔開的正整數，依次為 $f_1,f_2,\dots f_{N?1}$。

第三行一個整數 $Q$ ，表示共有 $Q$ 場合作需要安排。

接下來 $Q$ 行，每行描述一場合作：開頭是一個整數 $m$（$2\le m\le N$），表示參與本次合作的員工數量；接著是 $m$ 個整數，依次表示參與本次合作的員工編號（保證編號合法且不重復）。

保證公司結構合法，即不存在任意一名員工，其本人是自己的直接或間接領導。

輸出格式

輸出 $Q$ 行，每行一個整數，依次為每場合作的主持人選。

輸入輸出樣例 #1

輸入 #1

5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4

輸出 #1

2
2
0

輸入輸出樣例 #2

輸入 #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

說明/提示

樣例解釋 1

對于第一場合作，員工 $3,4$ 有共同領導 $2$ ，可以主持合作。

對于第二場合作，員工 $2$ 本人即可以管理所有參與者。

對于第三場合作，只有 $0$ 號老板才能管理所有員工。

數據范圍

對于 $25\%$ 的測試點，保證 $N\le 50$。

對于 $50\%$ 的測試點，保證 $N\le 300$。

對于所有測試點，保證 $3\le N\le 10^5$，$Q\le 100$，$m\le 10^4$。

---

2024/2/8 添加一組 hack 數據。

solution

題目要求找編號最小的共同祖先，比較高效的做法是找出每個節點的歐拉序，這樣就可以保證同一個子樹的序列是連續的，對于每一組數據，只用根據最大的歐拉序和最小的歐拉序就可以確定其公共祖先了。

代碼

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"using namespace std;int n, m, dfn[100001], dfm[100001], x, id = -1;
vector<int> son[100001];void dfs(int u){dfn[u] = ++id;for(int v : son[u]){dfs(v);}dfm[u] = id;
}int dfs2(int u, int Ma, int Mi){int ans = u;for(int v : son[u]){if(dfn[v] <= Mi && dfm[v] >= Ma) {int t = dfs2(v, Ma, Mi);ans = max(ans, t);break;}}return ans;
}int main() {cin >> n;for (int i = 1; i < n; i++) {cin >> x;son[x].push_back(i);}dfs(0);cin >> m;for(int i = 0; i < m; i++){int k, Ma = 0, Mi = n - 1;cin >> k;for(int j = 0; j < k; j++){cin >> x;Mi = min(Mi, dfn[x]);Ma = max(Ma, dfn[x]);}cout << dfs2(0, Ma, Mi) << endl;}
}

結果