企业官网建设流程全解析

. 解法 .#

前置知识 #

欧拉序#

在树上做一次深度优先遍历(DFS)，每当到达一个节点(无论是首次进入,还是处理完所有子节点后回溯回来)，就把该节点记录下来，由此得到的节点序列称为欧拉序(Euler tour)。
一种较为形式化描述是：
从根节点 root 开始执行以下递归过程：

是

否

开始: dfs u

记录节点 u 到欧拉序

还有未处理的子节点?

取下一个子节点 v

递归调用 dfs v

记录节点 u 到欧拉序

结束

RMQ#

RMQ 问题指区间最值查询（Range Minimum/Maximum Query）。

欧拉序与RMQ问题 #

好了，了解完前面的知识，我们就要引出一个重要性质：

性质1#

记 为节点 u 第一次在欧拉序中出现的位置。
对于任意两个节点 u,v，设 ,
则:

即区间 [l,r] 中深度最小的节点就是 u 与 v 的最近公共祖先。

#

设 。节点 和 分别位于 的不同子树中，或者其中一个就是 本身。
考察从首次进入 到首次进入 这段欧拉序对应的遍历过程：当 DFS 首次到达 （位置 ）后，算法会回溯到 ，再向下进入 （到达位置 ）。因此 必然在区间 内至少出现一次。
对于该区间内的任意一个节点 ，它出现在 到 之间，意味着在从 回溯到 并前往 的过程中访问了 。由 DFS 的性质，这期间访问的所有节点都位于 的子树中（包括 本身）。故有：

当且仅当 时等号成立。因此，区间 内深度最小的节点恰好就是 ，即：

证毕。

RMQ求法 #

你该不会认为这章最简单吧
你该不会直接套ST表吧，很显然，还是太不优秀了
当然不会直接套 ST 表。注意到我们的欧拉序有一个极其特殊的性质：相邻两个元素的深度差恰好为 。这引出了解决一般 RMQ 问题最优秀的算法之一——RMQ，它可以将预处理复杂度压到真正的 ，同时保持 查询。

RMQ 算法#

我们面对的序列 （此处 ，即欧拉序长度）满足：

我们要在线回答 的位置。
算法的核心思想是分块 + 状态压缩
第一步：分块与块间稀疏表
令块大小 （在 时 ）。将序列划分为 个块。
对块的最小值建立稀疏表（Sparse Table）。具体地，令 第块中的值，在数组 上运行标准 ST 表预处理。这一步时空复杂度均为 ，由于 ，这其实是 的。
第二步：块内本质类的数量
对于块内查询，若对整个数组的每一块都暴力跑 ST 表或全预处，空间会爆炸。但注意到 性质把块内的“形状”限制在极小的范围内。
考虑任意一个长度为 的块，对其内部元素作差分：

因此，给定该块的首元素值，整个块由这个长度为 的 差分序列唯一决定其相对形态。差分序列总共只有 种。由 ，得种类数约为：

这是一个远远小于 的数量级（ 时约 多种）。
第三步：块内查询的预打表
对于这至多 种差分类型，我们完全可以预处理出每一种类型在任意区间 （）内的最小值位置。
第四步：回答查询
对于一个查询 ：

• 若 在同一块内，直接用块内预打表结果，。
• 若跨块，则区间被分为：左端块的后缀 + 中间若干整块 + 右端块的前缀。
  • 左端块后缀、右端块前缀：分别用块内预打表 得到最小值位置。
  • 中间整块：在第一步的块稀疏表上做一次 RMQ。
  • 在得到的至多三个候选位置中，比较它们在原序列 中的深度，选取最小的那个。。

. 时间复杂度分析 .#

符号约定与基础规模#

设树有 个节点。进行一次深度优先遍历（DFS）得到欧拉序，欧拉序的长度 具有如下性质：

性质2（欧拉序长度）
对于 ，欧拉序的长度 。
证明.在DFS过程中，每个非根节点被记录两次：一次进入，一次回溯至父节点；根节点被记录一次进入，且最后一次回溯不产生新的记录。总计记录次数为 。
故 ，在后继复杂度分析中可直接视 与 同阶。

我们的目标是在序列 （此处 ）上支持区间最小值位置查询，并且序列满足 性质：

分块与块间稀疏表#

令块大小 。将 划分为 个块，记第 个块的最小值（按深度）为 。

对数组 建立稀疏表（Sparse Table），以支持在 时间内查询任意连续块区间的最小值位置。稀疏表的预处理时间复杂度为 ，空间复杂度也为 。

块间稀疏表复杂度计算：
已知 ，于是块数

代入稀疏表开销：

因此块间稀疏表的预处理时间与空间均为 。

块内本质类的数量与预打表#

对于任意一个长度为 的块，给定其首元素的值，该块的相对形态完全由长度为 的差分序列

决定。因此可能的差分序列种类数为

由 的定义可得上界：

故 ，种类数量远小于 。

对每一种差分类型，我们都可以预处理出一个 的查询表，存放该块内所有区间 （）上最小值的位置（相对于块起始的偏移）。构建该表的时间为 ，空间也为 。

块内预打表复杂度计算：
类型数 ，每类耗时 ，因此总预处理时间为

同样，块内打表所需额外空间为 。

单次查询的时间复杂度#

对于一次区间查询 ，分为两种情况：

1. 若 与 位于同一块内：直接使用该块对应的块内预打表，在 时间内返回最小值位置。
2. 若 与 跨越多个块：
   • 左端块的后缀查询：使用块内预打表，；
   • 中间连续整块的查询：使用块间稀疏表进行一次 RMQ，；
   • 右端块的前缀查询：使用块内预打表，；
   • 比较上述至多三个候选位置的深度值，取深度最小者，。

因此无论何种情形，单次查询均可在严格 时间内完成。

总体复杂度#

将欧拉序生成、深度数组计算、 RMQ 预处理与单次查询的开销汇总如下：

阶段	时间复杂度	空间复杂度
DFS 生成欧拉序、深度及首次出现位置
块间稀疏表预处理
块内本质类预打表	（亚线性）	（亚线性）
总预处理
单次 LCA 查询	—

. 代码实现 .#

自己写，不要总想抄。这是信息学竞赛，不是文科。
以P3379为题

#include<bits/stdc++.h> using namespace std; int block_size; vector<int> eul,dep,fst; vector<vector<int>> tree; vector<int> block,belong,lookup; void dfs(int now,int pre,int step){ dep[now]=step; eul.push_back(now); fst[now]=min(fst[now],(int)eul.size()-1); for(int i=0;i<tree[now].size();i++){ if(tree[now][i]==pre){ continue; } int nxt=tree[now][i]; dfs(nxt,now,step+1); eul.push_back(now); } return ; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,s; cin >> n >> m >> s; fst.resize(2*n+1,INT_MAX); dep.resize(n+1); tree.resize(n+1); for(int i=0;i<n-1;i++){ int x,y; cin >> x >> y; tree[x].push_back(y); tree[y].push_back(x); } eul.reserve(2*n-1); dfs(s,-1,0); int len=eul.size(); vector<int> dep_eul(len); for(int i=0;i<len;++i) dep_eul[i]=dep[eul[i]]; int B=1; if(len>2){ int log_len=31-__builtin_clz(len); B=max(1,log_len/2); } int nb=(len+B-1)/B; block.resize(len); vector<int> type(nb,0); for(int i=0;i<len;++i) block[i]=i/B; for(int b=0;b<nb;++b){ int L=b*B,R=min(len,L+B); int mask=0; for(int i=L+1;i<R;++i) if(dep_eul[i]>dep_eul[i-1]) mask|=(1<<(i-L-1)); type[b]=mask; } int tot=(B>1)?(1<<(B-1)):1; lookup.assign(tot*B*B,0); for(int mask=0;mask<tot;++mask){ vector<int> rel(B,0); for(int i=1;i<B;++i){ if((mask>>(i-1))&1) rel[i]=rel[i-1]+1; else rel[i]=rel[i-1]-1; } int base=mask*B*B; for(int l=0;l<B;++l){ int p=l; for(int r=l;r<B;++r){ if(rel[r]<rel[p]) p=r; lookup[base+l*B+r]=p; } } } vector<int> bmin(nb); for(int b=0;b<nb;++b){ int L=b*B,R=min(len,L+B); int best=L; for(int i=L+1;i<R;++i) if(dep_eul[i]<dep_eul[best]) best=i; bmin[b]=best; } int K=0; while((1<<K)<=nb) ++K; vector<vector<int>> st(nb,vector<int>(K)); for(int i=0;i<nb;++i) st[i][0]=bmin[i]; for(int j=1;j<K;++j){ for(int i=0;i+(1<<j)-1<nb;++i){ int a=st[i][j-1],b=st[i+(1<<(j-1))][j-1]; st[i][j]=dep_eul[a]<dep_eul[b]?a:b; } } auto qblock=[&](int b,int l,int r)->int{ int idx=type[b]*B*B+l*B+r; return b*B+lookup[idx]; }; auto rmq=[&](int l,int r)->int{ if(l>r) swap(l,r); int bl=block[l],br=block[r]; if(bl==br) return qblock(bl,l-bl*B,r-bl*B); int a1=qblock(bl,l-bl*B,B-1); int a2=qblock(br,0,r-br*B); int best=dep_eul[a1]<dep_eul[a2]?a1:a2; if(bl+1<=br-1){ int midlen=br-bl-1; int k=31-__builtin_clz(midlen); int m1=st[bl+1][k]; int m2=st[br-(1<<k)][k]; int amid=dep_eul[m1]<dep_eul[m2]?m1:m2; if(dep_eul[amid]<dep_eul[best]) best=amid; } return best; }; while(m--){ int u,v; cin>>u>>v; int l=fst[u],r=fst[v]; if(l>r) swap(l,r); int pos=rmq(l,r); cout<<eul[pos]<<'\n'; } return 0; }

作者：LiQirui