mhy写此题写了良久啊然后T啊T,T啊T.然后我去翻了一下seter的博客.结合他的东西yy出一种比较优越的做法.
如果我是出数据的,我会出两种数据,菊花图和链.
如果是菊花图,直接朴素ovoovo如果是链,可以以每个叶子节点为根建一次可持久化线段树.
如果是链上长出了一团菊花…
how to 结合?
不停地删叶子.如果删到某层时叶子足够少了,那就建可持久化线段树去.
对于询问,有若干种情况.
标记每个根里离得很近的点.
如果两个中有一个被标记过,那么直接以这个根求另一个的答案,然后朴素查找近的这个点到根的答案.
如果两个点都没有被删 ,那一定有至少一个根可以使得这条链的两个端点有祖先关系.这样的话直接用可持久化线段树求解.
好像完了?然后wa了ovoovo
还有一种情况是某个点被删了,但是删之后它是接在树枝上的!
于是它离根很远,还不一定有能搞出祖先关系的解.
于是先爬行到没被删的地方,看两个端点是否在同一棵被删的叶子树上.
如果是就朴素了.
如果不是的话,先求没被删的这一段,再朴素被删的一段.
终于完辣.
从来没写过这种代码.感觉自己萌萌哒.