【每日一题之暑假特别计划】7月8日精讲—Alliances

活动时间：7月7日起至9月1日
活动内容：写当日题解，活动时间内一共写满30篇每日一题的题解
活动奖励：即可额外获得牛客T恤一件
活动目的：滴滴滴～想充实的过完这个暑假嘛～快来写每日一题～每天都要进步喔～提升自己的同时还有超多福利喔～

每日一题交流群，群内定期有福利发放，群号：659028468

今日每日一题预告
题号 NC13950
名称 Alliances
来源 牛客练习赛2
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

先任意找一个点作为根，要知道帮派控制的路径肯定需要知道LCA——使用LCA找到这些帮派占领的最高点（共同的LCA），帮派进行联盟的时候用他们分别的LCA再求LCA。此时首都有三个情况：
1.不是这个LCA的子孙，此时所求的距离就是它到这个LCA的距离；
2.如果首都是直接被占领的城市，他和某个帮派（直接）占领的城市求LCA就会是他自己（也就是说他的某个儿子被占领了），但是我们肯定不能去枚举帮派占领的城市，我们考虑去帮派（直接）占领的城市里面找一个最有可能是首都儿子的城市，显然是dfs序（就是dfs的顺序）中它右边第一个被占领的城市；
3.如果首都是LCA的子孙但是没有被占领，可以把dfs序中他左边和右边离他最近的两个点拿出来和首都求LCA，这两个LCA里面一定有一个是离它最近的。（情况2其实可以合并在3里面处理）
在DFS序上找离一个点最近的左边和右边的点需要用到二分。

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目7月15日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴

提醒：更新昨天题解!
看完邓老师的题解，记得自己去做题提高呀~