P10113 [GESP202312 八级] 大量的工作沟通 题解
题目传送门
好像没有用欧拉序做的题解（ ？）
题意
- 给出一棵有
n 个节点的树，节点从0 到n-1 编号，且0 号节点是根节点 - 给出
Q 次询问，每次询问给出一个长度为m 的节点序列x_{1} , x_{2} , ... , x_{m} 你需要求出这些节点 编号最大的公共祖先（注意不是最近公共祖先）
思路
- 这道题也是一道求公共祖先的题，我们可以考虑将其转换为我们熟悉的最近公共祖先 (LCA) 问题。稍加思考我们可以发现，只需要记录每个节点到根节点的路径上编号最大的点，在求出 LCA 时将其输出即可
这不是个人都能想到吗你说这么多 - 而求
m 个点的 LCA ，只用求出两两的 LCA 后将其合并即可 - 对于 LCA 问题，我们一般有如下处理方式：
- 倍增求 LCA
- Tarjan 求 LCA （注意：这是一种离线算法）
- 树链剖分
- 欧拉序 + ST 表
- 这里主要介绍第四种方式
算法介绍
-
欧拉序
这里记节点
x,y 的最近公共祖先为lca(x,y) ，下文同对一棵节点数为
n 的树进行深度优先遍历时，在每一个节点到达时记录其编号，得到一个长度为2n-1 的序列，称为欧拉序。这棵树的欧拉序为：
1，2，5，2，6，9，6，2，1，3，7，3，1，4，8，4，1 . -
有了欧拉序，如何求 LCA 呢？
假设我们要求
lca(x,y) 记
x,y 在欧拉序中第一次出现的位置分别在l_{x},l_{y} ( 这里假定l_{x} < l_{y} ) 则闭区间[l_{x},l_{y}] 之间深度最小的节点就是lca(x,y) 这属于可重复贡献问题，可以用 ST 表求解
一些问题
-
欧拉序的长度为什么恰好是
2n-1 ？对于这棵有根树而言，如果一个节点
t 有x 个孩子，那么它将在欧拉序中出现x+1 次( 每个孩子回溯时将到达
t ，t 的父亲向下探索时也将到达t ，共x+1 次 )另一方面，这棵树除了根节点，其他节点均是某个节点的孩子，即所有节点共有
n-1 个孩子，将重复出现n-1 次，所以欧拉序长度为n+n-1=2n-1 . -
为什么则欧拉序中闭区间
[l_{x},l_{y}] 之间深度最小的节点就是lca(x,y) ？我不会证这里只做简单说明帮助大家理解设
x,y 的简单路径上的节点构成的序列为S ，则由欧拉序的定义可知：S \subseteq [l_{x},l_{y}] 又因为
lca(x,y) 是序列S 中深度最小的节点，因此现只需要说明lca(x,y) 同为[l_{x},l_{y}] 中深度最小的节点假设有一异于
lca(x,y) 的节点d' 满足d' \in [l_{x},l_{y}] 且深度不大于lca(x,y) 显然
d' 不在以lca(x,y) 为根的子树中，与欧拉序的生成过程矛盾这个矛盾说明
lca(x,y) 为[l_{x},l_{y}] 中深度最小的节点 -
时间复杂度？
预处理ST表：
O(n \log n) 查询：
O(Qm) 总时间复杂度：
O(n \log n + Qm)
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
vector<int> adj[maxn];// vector邻接表存图
int dep[maxn],dfn[maxn<<1],l[maxn],gr[maxn],cnt;
// gr表示本节点到根节点经过的节点的最大编号
// 其他数组含义如上述
int lg2[maxn<<1],st[maxn<<1][25];
void dfs(int cu,int pr) {
dfn[++cnt]=cu;
l[cu]=cnt;
dep[cu]=dep[pr]+1;
gr[cu]=max(cu,gr[pr]);
for(int to:adj[cu]) {
dfs(to,cu);
dfn[++cnt]=cu;
}
}
void init(){ // ST表初始化 + 线性求log
lg2[0]=-1;
for(int i=1;i<=cnt;++i) {
st[i][0]=dfn[i];
lg2[i]=lg2[i>>1]+1;
}
for(int i=1;i<=lg2[cnt];++i) {
for(int j=1;i<=lg2[cnt-j+1];++j){
st[j][i]=dep[st[j][i-1]]<dep[st[j+(1<<(i-1))][i-1]]?
st[j][i-1] : st[j+(1<<(i-1))][i-1];
}
}
}
void query(int n){
int lca;
scanf("%d",&lca);
while(--n) {
int x;
scanf("%d",&x);
if(l[lca]<l[x]) lca^=x^=lca^=x; // 异或交换两个元素，等价于swap()
int k=lg2[(l[lca]-l[x]+1)];
lca=dep[st[l[x]][k]]<dep[st[l[lca]-(1<<k)+1][k]]?
st[l[x]][k] : st[l[lca]-(1<<k)+1][k]; // O(1)查询lca
}
printf("%d\n",gr[lca]);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1,x;i<n;++i){
scanf("%d",&x);
adj[x].push_back(i);
}
dfs(0,0);
init();
int m;
scanf("%d",&m);
while(m--) {
scanf("%d",&n);
query(n); // 回答本次询问
}
return 0;
}第一次写题解，不足之处望海涵