感觉长脑子了。
考虑在路线两端点的 \(lca\) 计算贡献，那么线段可以分两类：
- \(u\) 为 \(v\) 祖先。
- \(u,v\) 互不为祖先。
设 \(dp_i\) 表示只考虑 \(i\) 子树内的路线时的答案。
引理 \(1\)：若插入一条以 \(i\) 为 \(lca\) 的路径会使以 \(i\) 的儿子为 \(lca\) 的路径数量减少，一定不优。
正确性显然。根据这一条性质，我们就可以不用维护儿子中具体的路径了，只需要维护 \(f_{i,j}\) 表示以 \(i\) 为根的子树中，能不能满足 \((i,j)\) 上没有边被使用且不使答案减小。
首先 \(i\) 的所有 \(1\) 类路径，能插就插，一定最优，没他一定不优。
其次剩下部分就是一般图最大匹配，\(dfs\) 即可，时间复杂度 \(O(sn^22^sn)\)
标签：题解,路径,CERC2014,sn,lca,Parades From： https://www.cnblogs.com/chang-an-22-lyh/p/18620040