顺序对的值:

有多种算法。可以枚举中间点，向左右两边扫描，假设左边有X个比它小，右边有Y个比它大，则将X*Y加入到最终答案。

复杂度O(n^2)。也可以枚举左边点，向右边扫描，维护一个单调的栈。

网络的关键边：

首先不难发现，如果一条边不影响整个图的连通性，那么该边一定不是关键边，那么关键边一定是割边。

而并不是所以割边都是关键边，我们考虑删除某条割边，将图分成两个集合，按照题意，要使得某个集合中不存在提供A服务或者B服务的点，该边即为关键边。使得某个集合中不存在提供A服务或者B服务的点，换句话说，就是对于其中某个集合，必须包含A服务和B服务点，但不能包含全图所有A服务或B服务点（否则另一个集合就不存在A或B点了）。

那么我们可以在tarjan算法求割边的时候，维护一下一个子树的A服务点以及B服务点的数量，当求出一条割边时，可以立即判断是否为关键边。

复杂度：O(n+m)。

大内密探:

第一问是经典的树形DP入门题。

第二问则需要在DP过程中做一些处理。

f0[i]代表以i为根节点，i不选且i的儿子也不选的情况下最少选多少个点

f1[i]代表以i为根节点，i不选且i的儿子中至少有一个选的情况下最少选多少个点

f2[i]代表以i为根节点，i选的情况下最少选多少个点

然后我们用g0[i],g1[i].g2[i]分别代表f0,f1,f2情况下的方案数。

那么若u是v的父亲：

f0 由 f1[v]推得；

f2 由 f0[v], f1[v], f2[v]中的最优值推得；

f1的情况则比较复杂，儿子们可以选择f1，也可以选择f2，但是至少有一个选择f2。下面介绍一种比较简便的算法。我们枚举儿子中第一个选择f2的，那么该儿子之前的必须选f1,而后面可以选f1,也可以选f2。我们维护前缀的只选f1的情况，维护后缀的f1,f2都可以选的情况，这样就能在O(儿子个数)的时间内维护f和g。

总复杂度O（n+m）

标程链接：

顺序对的值;

网络的关键边;

大内密探;

对算法有疑问的同学或者有其他的想法想要交流的同学请在下面留言~