P5838:
法一:直接树链剖分,然后统计U->LCA->V的区间内是否存在目标值,因为树剖性质,大区间不会被分成超过log段,不用担心T
法二:比较奇妙,将每个询问挂在U,LCA,V上将LCA设为入标记,U,V设为出标记,在入标记将目标值加入查询序列,并对每个查询值维护一个数组,若当前搜索到的节点为该值就+1,。搜索到出点时就通过减法减去入点的标记,查看此区间是否有目标值。
CF1528C:
这些点在第一棵树中是链,所以在搜索时标记该节点在第二棵中的管辖区间,如果冲突了就删掉大的区间。统计答案。
[NOIP2016 提高组] 天天爱跑步:
若有路径S->LCA->T,当有观察点x在S->LCA中观察到该玩家则有w[x]=dep[S]-dep[X],所以dep[s]=w[x]+dep[x],将dep[s]区间加入这条链上,则对于x是统计x上有几个w[x]+dep[x],使用树上差分+瞎搞完成。另一条链也类似操作。