【題目敘述】https://open.kattis.com/problems/boxes
【解題想法】最近共同祖先 (LCA), 稀疏表 (Sparse Table), 倍增法
- vector<int> v[maxn]：adjacency list，存圖（某個盒子內有哪些盒子）
- p[maxn][20]：紀錄每個節點的 2^i 倍祖先 (2^20 = 1e6 > 200000) ，for LCA
- siz[maxn]: subtree size of each node (每個盒子及其內含的盒子總數)
- dep[maxn]: depth of each node，紀錄每個盒子位處第幾層。(虛構的節點-0，假想有一個超大的盒子，所有的盒子都放置其中。)
- 讀入測資
- p[i][0]：第i個節點的parent (2^0 倍祖先)
- v[p[i][0]].push_back(i); 第p[i][0]個盒子裏多了「盒子-i」
- p[j][i] = p[p[j][i-1]][i-1]; 「節點-j」的 2^i 倍祖先 等於 「節點-j」的 2^(i-1) 倍祖先的 「2^(i-1) 倍祖先」
- DFS計算每個節點的深度及其子樹的節點數目。
- LCA查詢某個盒子是否處於其它的盒子內，如果是的話，不重複計算這個盒子及其內含的盒子數目。
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 200000;
int n, Q, p[maxn][20], root, siz[maxn], dep[maxn], tmp, q[20], ans;
bool flag;
vector <int> v[maxn];
int dfs(int node, int d){
dep[node] = d + 1;
if (v[node].empty()){
siz[node] = 1;
return 1;
}
int total = 1;
for (int i:v[node]){
total += dfs(i, d+1);
}
siz[node] = total;
return siz[node];
}
int lca(int a, int b){
if (dep[b] < dep[a]) swap(a, b);
if (dep[a] != dep[b]){
int dif = dep[b] - dep[a];
for (int i = 0; i < 20; i++){
if (dif & 1) b = p[b][i];
dif >>= 1;
}
}
if (a == b) return a;
for (int i = 19; i >= 0; i--){
if (p[a][i] != p[b][i]){
a = p[a][i];
b = p[b][i];
}
}
return p[a][0];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++){
cin >> p[i][0];
v[p[i][0]].push_back(i);
}
for (int i = 1; i < 20; i++){
for (int j = 1; j <= n; j++){
p[j][i] = p[p[j][i-1]][i-1];
}
}
dfs(0, 0);
cin >> Q;
while (Q--){
cin >> tmp;
ans = 0;
for (int i = 0; i < tmp; i++){
cin >> q[i];
}
if (tmp == 1) cout << siz[q[0]] << "\n";
else{
for (int i = 0; i < tmp; i++){
flag = true;
for (int j = 0; j < tmp; j++){
if (i == j) continue;
if (lca(q[i], q[j]) == q[j]){
flag = false;
break;
}
}
if (flag) ans += siz[q[i]];
}
cout << ans << "\n";
}
}
}