P1035 · OFFICIAL SOLUTION

P1035 双径会深庭官方题解

Gioush OJ · P1035 双径会深庭

双径会深庭

【题意简述】

给定一棵 $n$ 个结点的树。每次询问给出 $s_1,t_1,s_2,t_2$ ，判断路径 $(s_1,t_1)$ 与路径 $(s_2,t_2)$ 是否至少经过同一个结点。

【Hint】

【提示】

设两条路径的最近公共祖先分别为 $p_1,p_2$ 。若两条路径相交，则 $p_1$ 位于第二条路径上，或 $p_2$ 位于第一条路径上。

【数据点 1∼51\sim 51∼5】

对每次询问分别从 $s_1$ 与 $s_2$ 出发搜索，恢复两条简单路径，并标记路径上的全部结点。扫描全部结点，只要存在一个结点同时属于两条路径，答案就是 Yes。

每次询问需要两次搜索和一次扫描，时间复杂度为 $\mathcal{O}(nq)$ ，空间复杂度为 $\mathcal{O}(n)$ 。

【数据点 6∼106\sim 106∼10】

特殊性质保证整棵树是一条链。找到度数为 $1$ 的端点后，沿链确定每个结点的位置。路径 $(s,t)$ 便对应位置轴上的闭区间

[\min(\operatorname{Pos}(s),\operatorname{Pos}(t)),\max(\operatorname{Pos}(s),\operatorname{Pos}(t))].

两条路径相交当且仅当两个闭区间相交。预处理需要 $\mathcal{O}(n)$ 的时间，每次询问为 $\mathcal{O}(1)$ 。

这一档说明，我们不必恢复路径本身，只需要能够用少量端点信息判断一个结点是否位于路径上。

【数据点 11∼1511\sim 1511∼15】

这一档只有 $q\leq 300$ ，仍然可以使用第一档的路径标记，时间复杂度为 $\mathcal{O}(nq)$ 。

去掉对 $q$ 的限制后，需要支持两件事：求一条路径中深度最小的结点，以及判断一个结点是否位于给定路径上。这两件事都可以通过最近公共祖先完成。

【正解】

任选结点 $1$ 为根，倍增预处理 $\mathbf{LCA}$ 。树上距离为

\operatorname{Dist}(u,v)=\operatorname{Depth}(u)+\operatorname{Depth}(v)-2\operatorname{Depth}(\mathbf{LCA}(u,v)).

结点 $x$ 位于路径 $(u,v)$ 上，当且仅当

\operatorname{Dist}(u,x)+\operatorname{Dist}(x,v)=\operatorname{Dist}(u,v).

令

p_1=\mathbf{LCA}(s_1,t_1),\qquad p_2=\mathbf{LCA}(s_2,t_2).

两条路径相交当且仅当 $p_1$ 位于路径 $(s_2,t_2)$ 上，或者 $p_2$ 位于路径 $(s_1,t_1)$ 上。

【正确性证明】

若 $p_1$ 位于第二条路径上，则 $p_1$ 同时位于第一条路径与第二条路径，两条路径相交。 $p_2$ 的情况同理，因此判定的充分性成立。

接下来证明必要性。假设两条路径相交，令 $z$ 为交集中深度最小的结点。由于 $z$ 分别位于两条路径上，所以 $p_1,p_2$ 都是 $z$ 的祖先。树上同一结点的祖先构成一条链，因此 $p_1,p_2$ 必然具有祖先关系。

不妨设 $p_1$ 的深度不小于 $p_2$ 。那么 $p_1$ 位于从 $p_2$ 到 $z$ 的祖先链上。由于 $p_2,z$ 都位于第二条路径上，二者之间的整段路径也属于第二条路径，所以 $p_1$ 位于第二条路径上。另一种深度关系同理，必要性成立。

综上所述，该判定是充要的。

【复杂度分析】

倍增预处理的时间复杂度为 $\mathcal{O}(n\log n)$ 。每次询问只进行常数次最近公共祖先与距离计算，时间复杂度为 $\mathcal{O}(\log n)$ 。总时间复杂度为 $\mathcal{O}((n+q)\log n)$ ，空间复杂度为 $\mathcal{O}(n\log n)$ 。

【参考代码】

1/*2- @Author: Ehundategh3- @Date: 2023-11-07 15:16:314- @FilePath: \Code\11.6\仓鼠找Sugar.cpp5- @Description: You Steal,I Kill6 */7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 10001011using namespace std;12int Fa[MAXN][21],Total,Head[MAXN],Depth[MAXN],In1,In2,In3,In4;13struct edge{14;;;;int St,Ed,Next;15}Edge[MAXN<<1];16void Edge_Add(int St,int Ed){17;;;;Edge[++Total]={St,Ed,Head[St]};18;;;;Head[St]=Total;19}20void DFS(int Now,int From){21;;;;Fa[Now][0]=From;22;;;;Depth[Now]=Depth[From]+1;23;;;;for(int i=Head[Now];i;i=Edge[i].Next){24;;;;;;;;int To=Edge[i].Ed;25;;;;;;;;if(To==From) continue;26;;;;;;;;DFS(To,Now);27;;;;}28}29int LCA(int a,int b){30;;;;if(Depth[a]<Depth[b]) swap(a,b);31;;;;for(int i=19;i>=0;i--){32;;;;;;;;if(Depth[Fa[a][i]]>=Depth[b]) a=Fa[a][i];33;;;;}34;;;;if(a==b) return a;35;;;;for(int i=19;i>=0;i--){36;;;;;;;;if(Fa[a][i]!=Fa[b][i]){37;;;;;;;;;;;;a=Fa[a][i];38;;;;;;;;;;;;b=Fa[b][i];39;;;;;;;;}40;;;;}41;;;;return Fa[a][0];42}43int Get(int a,int b){44;;;;int lca=LCA(a,b);45;;;;return Depth[a]+Depth[b]-2*Depth[lca];46}47bool Query(int a,int b,int c,int d){48;;;;int Lca1=LCA(a,b);49;;;;int Lca2=LCA(c,d);50;;;;int Dis1=Get(a,b);51;;;;int Dis2=Get(c,d);52;;;;int Judge1=Get(Lca1,c)+Get(Lca1,d);53;;;;int Judge2=Get(Lca2,a)+Get(Lca2,b);54;;;;if(Judge1==Dis2||Judge2==Dis1) return true;55// ;;;;if(LCA(Lca1,Lca2)==Lca2&&(LCA(Lca1,d)==Lca1||LCA(Lca1,c)==Lca1)) return true;56// ;;;;if(LCA(Lca1,Lca2)==Lca1&&(LCA(Lca2,a)==Lca2||LCA(Lca2,b)==Lca2)) return true;57;;;;return false;58}59void Solve(){60;;;;int n,q;61;;;;scanf("%d%d",&n,&q);62;;;;Total=0;63;;;;memset(Head,0,sizeof(int)*(n+1));64;;;;memset(Depth,0,sizeof(int)*(n+1));65;;;;memset(Fa,0,sizeof(int)*(n+1)*21);66;;;;for(int i=1;i<n;i++){67;;;;;;;;scanf("%d%d",&In1,&In2);68;;;;;;;;Edge_Add(In1,In2);69;;;;;;;;Edge_Add(In2,In1);70;;;;}71;;;;DFS(1,1);72;;;;for(int i=1;i<=19;i++){73;;;;;;;;for(int j=1;j<=n;j++){74;;;;;;;;;;;;Fa[j][i]=Fa[Fa[j][i-1]][i-1];75;;;;;;;;}76;;;;}77;;;;while(q-->0){78;;;;;;;;scanf("%d%d%d%d",&In1,&In2,&In3,&In4);79;;;;;;;;printf("%s\n",Query(In1,In2,In3,In4)?"Yes":"No");80;;;;}81}82int main(){83;;;;int c,T;84;;;;scanf("%d%d",&c,&T);85;;;;while(T-->0) Solve();86;;;;return 0;87}