震惊!我妻由乃当上了发明家!!!
传送门
题解
又是一道由乃OI的毒瘤题QwQ。
前置技能,这题的简化版:SNOI2017 一个简单的询问。
做完上面一题,不难发现,只要爬到树上做这题就行了。
先一巴掌把树拍扁按照DFS序将树化成一个序列,这样每一颗子树对应着序列上的一段区间,然后就和之前那一题没什么区别了。
但是!!!竟然有换根这种操作。
不过不难发现,其实换根的操作就是假的。
先设当前的根为$rt$,询问子树的节点为$x$,不管怎样,我们就认为根始终是节点$1$。
然后又这么几种情况:
- $x=rt$
此时询问的就是整棵树。
- $LCA(x,rt)\neq x$
此时查询的就是当$1$为根时$x$的子树。
- $LCA(x,rt)=x$
此时查询整棵树除去rt到x路径上离x最近的一个节点(就是图中好几个箭头指的那个点)的子树。可以拆成两个序列解决。那个节点可以通过倍增找到。
拆分成若干个序列之后,直接莫队即可。
还有记得要离散,权值是比较大的。我就因为没看数据范围,忘记离散,结果崩掉1个点QwQ
代码
1 |
|