【20181026T2】**图【最小瓶颈路+非旋Treap+启发式合并】 题面 【错解】 最大最小?最小生成树嘛 蛤?还要求和? 点分治? 不可做啊 写了个MST+暴力LCA,30pts,140多行 事后发现30分是给dijkstra的 woc 【正解】 树上计数问题:①并查集②启发式合并③点分治 其实可以启发式合并 跑一遍Kruscal,每次用数据结构维护满足条件的点对再乘上当前这条边的权值。因为排了序,所以这条边是最大的 复杂度大概(O(MlogM+Nlog_N^2)) 代码