交互题。

一棵以1为根的二叉树T,可以询问任意两点间的距离,目的是求出每个节点的父亲。

|T|\leq 10^3, q\leq 3\times 10^4

明显需要每个点的深度,询问dis(1,i)即可。

因为需要确认LCA的某些信息,所以按深度由小而大求比较合适。

假设已知所有dep\leq r的节点的父亲,现在考虑求\forall x,dep(x)=r+1的父亲。

假设随机询问一个深度为r的点yLCA(x,y)=z

这时候考虑给定的二叉树条件,那么就会有两种情况:

1 x,yz的同一个子树中,显然z=y,y就是x的父亲。

2x,y不在z的同一个子树中,假设y所在子树为ux所在子树为v,则以vLCA,递归进入v处理即可。

如果考虑求\forall x, dep(x)=r,那么当子树v内不存在另一个dep(y)=r,则转化为询问dep(y)=r-1,如果存在y,dep(y)=r,那么x,y为兄弟当且仅当两点的距离为2

考虑怎么维护子树内深度为r/r+1 的点,如果维护G_{x,k,\alpha},则每次维护G复杂度为O(n),总复杂度为O(n^2),询问不超过n\log n次。

2022.10.8补
上一篇 «
2022.10.6补
» 下一篇
© 2017 - 2024 云雀.
...... visits · ...... visitors