恭喜你发现一只写挂了却质疑自己贪心错了的纯纯sb。
首先一个简单的猜想就是维护每个子树内向上的路径，如果两个子树之间路径可以合并就合并。
但是这是有问题的，比如如果一对路径在之前匹配了，但是祖先处有两条不能匹配的路径，这样我们算出来需要 \(3\) 条，但是实际上 \(2\) 条就够了。
这个问题在于如果我们已经把两条直上直下的路径匹配了，我们之后如果要用就不太行。因此我们加入反悔机制，可以将一对已经匹配了的直上直下的路径拆开来。
现在貌似看上去就挺对了呢！我们来整理一下思路：
- 两棵子树合并的时候：首先将两颗子树内直上直下的路径合并，然后会有一边的路径比较多合并不完，那么就把比较少的那边已经匹配的路径拆掉和这边匹配。
- 加入一条以当前点为起点的路径时：看看还有没有直上直下的路径，如果有的话那么拉长深度最浅的一条，如果没有的话看看有没有已经匹配的，如果有那么拆了，否则新开一条。这里拆匹配的原因在于不拆是一对已经匹配的和一条直上直下的，如果不拆是两条直上直下的。显然两条直上直下的更有用一点，而总路径数是不变的，因此拆了不会更劣。
所以用个启发式合并 set 模拟就好了，时间复杂度 \(O(n\log ^2n)\)。
什么？你问我这个复杂度怎么过？ZJOI2022D1T2几乎一样的范围跑过了根号，那么两个 log 其实差不多（
标签：路径,匹配,luogu,P8341,合并,直上直下,子树,AHOI2022,如果 From： https://www.cnblogs.com/275307894a/p/17182888.html