题面

【错解】

最大最小?最小生成树嘛

蛤?还要求和?

点分治?

不可做啊

写了个MST+暴力LCA,30pts,140多行

事后发现30分是给dijkstra的

【正解】

树上计数问题:①并查集②启发式合并③点分治

其实可以启发式合并

跑一遍Kruscal,每次用数据结构维护满足条件的点对再乘上当前这条边的权值。因为排了序,所以这条边是最大的

复杂度大概\(O(MlogM+Nlog_N^2)\)

代码

05-06 02:53