BZOJ3083 遥远的国度

遥远的行星? 神奇的国度?

NO,遥远的国度.

这题真皮OVO

考虑换根之后只有两种情况答案会变

一是根与询问点重合 答案整棵树

二是在询问点的子树内,这时候需要……枚举子树树根!

然后用dfs序来判断,这玩意是连续的(嗯……?),而且在每个子树内也是连续的(!)

锁定在哪颗子树内!

然后你抓着这个子树的根节点把它拎起来,这整棵树其余的部分就耷拉到下面了

然后你就会发现这时候实际是询问这个红色的部分

然后就行了。

画风奇怪??

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据