【题解】牛客练习赛2

(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 Contest
观察符合题目要求的队A、B在三场比赛中的先后顺序会出现怎么样的情况。
无非两种，A>B出现两场，A<B出现一场； A>B出现一场，A<B出现两场； 分别观察第一场比赛、第二场比赛； 第一场比赛、第三场比赛； 第二场比赛、第三场比赛； 这三组比赛中A和B的顺序，如果在某一场比赛中A>B且另一场比赛中A<B，答案加一；
这个可以用逆序对做。
最后发现无论是哪种情况，合法的方案都会被加两次；
所以最后答案除以2就可以了。

T2 River
这种题目的通解就是二分导数计算时间然后看看总时间符不符合题目要求。
求导过程如下：

T3 Alliances
先看看一个帮派和一个点的最短距离是什么。
一个帮派会形成一棵树。这棵树的根节点是帮派中所有点的LCA。
如果首都在LCA上面或者LCA不在首都上面，那么答案就是LCA与首都的距离。
否则就找到帮派中DFS序在首都附近的两个点。前面一个后面一个，求LCA，答案为LCA与首都的距离取min。
看完了一个帮派的情况，再看看一个联盟的情况。
一个联盟实质上是做了一样的事情。
我从每个帮派中选一个点作为其代表点。那么联盟就可以用这些点来表示。重复一遍上面的过程，再与每个帮派的ans取min，即为答案。

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305