A.

　　单调栈，考虑每一对可行解必然是单调栈中相邻的两个点，注意处理元素相同的情况，需要存下单调栈里某一元素出现的个数，考试的时候脑抽打了hash表，然后虽然还是$O(n)$，但是T成了70。。。实际上，每个元素在单调栈里是连续的一段，因此直接用数组存一下就好。

B.　　

　　我思路和题解不一样，我是倒推的。

　　考虑某个点i被经过了多少次，只能由两种位置转移而来：$p_{j}=i$的$j$或$i-1$。

　　所以令f_{i}表示i被经过了多少次，有转移：

　　$$f_{i}=\sum \frac{f_{j}}{2}[p_{j}==i]+\frac{f_{i-1}}{2}$$

　　移个项 $f_{i-1}=2*f{i}-\sum f_{j}[p_{j}==i]$

　　起始：$f_{n+1}=1$

　　把f累加起来就是答案。然而我居然是直接除以2，没乘逆元。。。挂成40，居然有分。 

C.

　　考虑每条边，处理出经过它的最长路长度，那么删去一个点后，答案就是所有最长路没有经过该点的边。

　　考虑如何保证选择的边的最长路不经过这个点。

　　按照拓扑序每次选出一点，将它的所有入边删去，统计答案，加入它的所有出边即可保证这一点。