首先可以想到,如果整张图里面有一个可以走遍所有点的圈的话,那么只要把边定向成绕一圈的,就可以达到最大值 n^2 了.因此由这件事可以想到,考虑这张图的边双连通分量,那么可以先把每个边双连通分量内部都先弄成一个强连通分量,把他们都先整个缩起来,这样就可以得到一棵带权的树,所以之后只要处理树的情况就可以了.
最后补上我猜测的那个性质和另外一个性质的等价证明.首先从右推到左是显然的,所以只需处理从左推到右的情形,也就是接下来要证明"一条路径上至多改变一次方向"可以推到"存在一个点 X 满足那件事".随便取一个点 P,如果他已经满足 X 的条件的话那就证完了,因此我们可以假设存在两个点 A 和 B ,使得 P 走到 A 的路上的边都是指向 A 的,且 B -> A (反过来的话不影响证明).此时如果有另一个点 C 使得 C->A ,那么 C 所在的不包含 A 的那一整个子树里的边的方向就都确定了,全部都会是指往 C 的方向,否则就会违反先前假设的性质.再考虑其他由 A 指出去的边,如果这时候找不到另一个点 D ,使得 A 走到 D 的路径上全部都是指向 D 的边,但存在另一个点 E 使得 E->D ,那么取 A 为 X 就证完了.但这个过程不可能进行无限次,否则整棵树的大小为无限大,矛盾.因此总有一天会停下来,也就是我们一定找的到满足那个条件的 X .
对了,官方解里面是直接写了那个我等价之后的性质,然后说很多人都猜这件事是对的,也没证明为什么,就只有说这是一个 magic XDDD