D. Sum of Maximum Weights

给定一棵树，边有边权。计算所有点对路径上最大边权的权值和，范围 \(n\le 10^5\)

考虑类似 Kruskal 的过程添加树边，则每一条边加入时，对于连通的两个集合间的点对，最大边即为当前边。

因此在维护并查集的同时维护集合大小即可，贡献为 w \(\times\) Size(u) \(\times\) Size(v) ，复杂度 \(O(n\log n)\)

E. Packing Under Range Regulations

有 \(10^9\) 个盒子，每个盒子只能放一个球。有 \(n\) 个球，第 \(i\) 个要放在 \([l_i,r_i]\) 的某一个盒子中，问是否有解，范围 \(n\le 2\times 10^5\)

比较经典的贪心，考虑从左往右放，最紧急的需求肯定是右端点最小的。

按照右端点排序，依次考虑每个需求，尽量往左放，相当于区间查询最靠左的未覆盖位置，然后修改这个位置的覆盖状态。

实现可以选择动态开点线段树+线段树上区间内二分，我是用的是并查集维护下一个未覆盖的位置（疯狂的馒头）。

因为序列有 \(10^9\) 长，使用 unordered_map 维护并查集数组，具体实现见代码，复杂度 \(O(n\log n)\) 。

struct node {int l, r;} c[N];

inline bool operator < (const node &a, const node &b) {
    return a.r == b.r ? a.l < b.l : a.r < b.r;
}

unordered_map<int, int> nxt;

int find(int x) {
    return nxt[x] ? nxt[x] = find(nxt[x]) : x;
}

void work() {
    int n = rd();
    for (int i = 1; i <= n; ++i) {c[i].l = rd(); c[i].r = rd();}
    sort(c + 1, c + 1 + n);
    for (int i = 1, pos; i <= n; ++i) {
        if (!nxt[c[i].l]) {
            nxt[c[i].l] = c[i].l + 1; continue;
        }
        pos = find(c[i].l);
        if (pos > c[i].r) {puts("No"); return;}
        nxt[pos] = pos + 1;
    }
    puts("Yes");
}