【题目来源】https://www.luogu.com.cn/problem/P10113https://oj.czos.cn/p/3492https://bas.ssoier.cn/problem_show.php?pid4040【题目描述】某公司有 N 名员工编号从 0 至 N-1。其中除了 0 号员工是老板其余每名员工都有一个直接领导。我们假设编号为 i 的员工的直接领导是 fi。该公司有严格的管理制度每位员工只能受到本人或直接领导或间接领导的管理。具体来说规定员工 x 可以管理员工 y当且仅当 xy或 xfy或 x 可以管理 fy。特别地0 号员工老板只能自我管理无法由其他任何员工管理。现在有一些同事要开展合作他们希望找到一位同事来主持这场合作这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工他们希望找到编号最大的员工。你能帮帮他们吗【输入格式】第一行一个整数 N表示员工的数量。第二行 N-1 个用空格隔开的正整数依次为 f1f2…f_{N-1}。第三行一个整数 Q表示共有 Q 场合作需要安排。接下来 Q 行每行描述一场合作开头是一个整数 m2≤m≤N表示参与本次合作的员工数量接着是 m 个整数依次表示参与本次合作的员工编号保证编号合法且不重复。保证公司结构合法即不存在任意一名员工其本人是自己的直接或间接领导。【输出格式】输出 Q 行每行一个整数依次为每场合作的主持人选。【输入样例一】50 0 2 232 3 43 2 3 42 1 4【输出样例一】220【输入样例二】70 1 0 2 1 252 4 62 4 53 4 5 64 2 4 5 62 3 4​​​​​​​【输出样例二】21110【样例一解释】对于第一场合作员工 34 有共同领导 2 可以主持合作。对于第二场合作员工 2 本人即可以管理所有参与者。对于第三场合作只有 0 号老板才能管理所有员工。【数据范围】对于 25% 的测试点保证 N≤50。对于 50% 的测试点保证 N≤300。对于所有测试点保证 3≤N≤10^5Q≤100m≤10^4。【算法分析】● 树上倍增https://blog.csdn.net/hnjzsyjyj/article/details/156747410●​​​​​​​ 树链剖分https://blog.csdn.net/hnjzsyjyj/article/details/156956145● 树链剖分Heavy-Light DecompositionHLD是一种将树结构转化为线性序列的算法技巧常用于解决树上路径查询与修改‌以及‌子树查询与修改‌这两大类问题。其主要包括两个分解步骤1重链剖分‌将树的边分为“重边”和“轻边”。对于每个非叶子节点选择其所有子节点中‌子树大小最大‌的那一个连接这两点的边即为重边连接到其他子节点的边则为轻边。由重边相连形成的路径称为重链。2DFS 序重排‌通过一次深度优先搜索优先遍历重儿子从而保证‌每条重链上的节点在新的 DFS 序中是连续存储的‌。● 树链剖分的核心思想是通过两次 DFS 对树进行剖分将树分解为若干条“重链”并重新安排节点的访问顺序DFS 序使得每条重链上的节点在序列中连续存储同时每个子树内的节点也连续存储。这样复杂的树形操作就被转化为了对线性序列的区间操作可以借助线段树、树状数组等数据结构高效地完成。● 树链剖分的几个重要概念1重儿子 (Heavy Son)‌对于树中的一个非叶子节点其所有子节点中‌子树大小含子树的根的节点数最大‌的那个子节点称为该节点的重儿子。如果存在多个子节点子树大小相同可任意选取其中一个作为重儿子。2轻儿子 (Light Son)‌非叶子节点的所有子节点中除了重儿子以外的其他子节点都称为该节点的轻儿子。3重边 (Heavy Edge)‌连接一个节点与其重儿子的边称为重边。4轻边 (Light Edge)‌连接一个节点与其轻儿子的边称为轻边。5重链 (Heavy Path)‌由一系列连续的重边首尾相连形成的路径称为一条重链。整棵树可以被分解为若干条互不相交的重链。6链头 (Head of Chain / Top)‌每条重链的起始节点即这条链上‌深度最浅‌的那个节点称为该重链的链头。树根通常单独构成一条重链其本身即为链头。● 树链剖分的两个 dfs 函数1dfs1 函数。求解数组 dep[]、pre[]、son[]、siz[]int dep[N]; //dep[x] represents depth of node xint pre[N]; //pre[x] represents parent node of node xint son[N]; //son[x] represents heavy child of non-leaf node xint siz[N]; //siz[x] represents nu2dfs2 函数。求解数组 top[]int top[N]; //top[x] represents head node of the heavy chain where node x is located【算法代码一树链剖分 链式前向星】#includebits/stdc.h using namespace std; const int N1e55; int h[N],e[N1],ne[N1],idx; int dep[N],pre[N],son[N],siz[N],top[N]; int pos[N]; int tot; void add(int a,int b) { e[idx]b,ne[idx]h[a],h[a]idx; } void dfs1(int u,int fa) { pre[u]fa; dep[u](fa-1?0:dep[fa]1); siz[u]1,son[u]-1; int mx_size0; for(int ih[u]; i!-1; ine[i]) { int je[i]; if(jfa) continue; dfs1(j,u); siz[u]siz[j]; if(siz[j]mx_size) { mx_sizesiz[j]; son[u]j; } } } void dfs2(int u,int tpx) { top[u]tpx; pos[u]tot; if(son[u]!-1) { dfs2(son[u],tpx); } for(int ih[u]; ~i; ine[i]) { int je[i]; if(jpre[u]||json[u]) continue; dfs2(j,j); } } int LCA(int x,int y) { while(top[x]!top[y]) { if(dep[top[x]]dep[top[y]]) swap(x,y); xpre[top[x]]; } return dep[x]dep[y]?x:y; } int main() { ios::sync_with_stdio(0); cin.tie(0); memset(h,-1,sizeof h); int n; cinn; for(int i1; in; i) { int x; cinx; add(x,i),add(i,x); } dfs1(0,-1),dfs2(0,0); int T; cinT; while(T--) { int m,idx; cinmidx; int ansidx; for(int i1; im; i) { int t; cint; ansLCA(ans,t); } coutans\n; } return 0; } /* in: 5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4 out: 2 2 0 */【算法代码二树链剖分 邻接表】#includebits/stdc.h using namespace std; const int N1e55; vectorint tree[N]; int dep[N]; //dep[x] represents depth of node x int pre[N]; //pre[x] represents parent node of node x int son[N]; //son[x] represents heavy child of non-leaf node x int siz[N]; //siz[x] represents number of nodes in the subtree rooted at node x int top[N]; //top[x] represents head node of the heavy chain where node x is located int pos[N]; //pos[x] represents the position of node x in the DFS sequence int cur_pos; //The current position in the DFS sequence void dfs1(int u,int fa) { //Solving for dep[],pre[],son[],siz[] pre[u]fa; dep[u](fa-1?0:dep[fa]1); siz[u]1; son[u]-1; //-1 indicates no heavy son int mx_size0; for(int j:tree[u]) { if(jfa) continue; dfs1(j,u); siz[u]siz[j]; if(siz[j]mx_size) { mx_sizesiz[j]; son[u]j; } } } void dfs2(int x, int topx) { //Solving for top[] top[x]topx; pos[x]cur_pos; if(son[x]!-1) { dfs2(son[x],topx); } for(int j:tree[x]) { if(jpre[x] || json[x]) continue; dfs2(j,j); //thin son starts a new chain } } int LCA(int x, int y) { //cal LCA using Tree Chain Division while(top[x]!top[y]) { if(dep[top[x]]dep[top[y]]) { swap(x,y); } xpre[top[x]]; } return dep[x]dep[y]?x:y; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cinn; for(int i1; in; i) { int x; cinx; tree[x].push_back(i); tree[i].push_back(x); } //Initialize Tree Chain Division cur_pos0; dfs1(0,-1); dfs2(0,0); int T; cinT; while(T--) { int m,idx; cinmidx; int ansidx; for(int i1; im; i) { int t; cint; ansLCA(ans,t); } coutans\n; } return 0; } /* in: 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 out: 2 1 1 1 0 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/156988831https://blog.csdn.net/hnjzsyjyj/article/details/156956145https://blog.csdn.net/hnjzsyjyj/article/details/162441877https://gesp.ccf.org.cn/101/attach/1584918480027680.pdfhttps://ti.luogu.com.cn/problemset/https://blog.csdn.net/weixin_60445850/article/details/147918344https://www.luogu.com.cn/problem/solution/P10113