DSU on tree

即树上启发式合并。
算法流程通常是通过dfs处理出树上每个点的重儿子，然后通过一个dfs算法来计算答案。对于一个节点，我们从重儿子继承信息，暴力合并轻儿子的信息，同时处理出每个点/点对/...对答案的贡献。
如果我们暴力合并轻儿子的时间复杂度和轻子树的大小成线性关系，那么由重链剖分的性质，一个点到根的路径最多有\(\log n\)条轻边，那么每个点的贡献实际上是\(logn\)级的，那么总的合并轻子复杂度为\(O(n\log n)\)(实际上这个常数很小，因为每个点最多只有\(\log n\)次贡献，很多点取不到这么大)
我们继承重子的操作数量级是\(O(n)\)的，如果我们可以确保每次继承重子的复杂度在\(O(1)\)或者\(O(\log n)\)的话，那么启发式合并总的时间复杂度在\(O(n\log n)\)。
启发式合并的空间复杂度取决于具体的实现方式，如果按照oi-wiki上的方法，两次遍历轻子的话，空间复杂度可以达到\(O(n)\),如果不做这样的操作(或者这样的操作不太好实现)的话，复杂度取决于记录贡献用的容器，如果是vector作为桶的话，可能会到\(O(n\log n)\),如果是map的话可能还\(O(n)\)。

下面是近期做的一些dsu on tree

T1 NC2025winter Round5 G

题目大意

一颗树，有点权\(w\)，求三元组\((x,y,z)\)数量，其中\(x < y, w_x = w_y,w_x < w_z\),且\(z\)在\(x\)到\(y\)的路径上。

分析

由于是求三元组，我们可以枚举节点\(z\)(这个更特殊一些)，然后计算合法的\(x,y\)对的数量。
如果是暴力枚举，我们需要以每个点为根搜一遍所有子树并且统计信息，时间复杂度为\(O(n^2)\)。
我们考虑使用dsu on tree的思想得到一个较优的枚举方案，同时想出一个合适的计算贡献方案，可以利用继承重子的信息。这里我们可以随意指定一个根，下面所说子树均是以一个固定点为根的子树。
统计时，我们可以用一个(unordered_)map来统计一个节点子树内权值为\(w\)的点出现了\(c_w\)次。
对于一个点\(p\)，我们把以该节点为\(z\)的贡献分成两部分：
1. 子树内相互贡献(点\(p\)不同子节点的子树相互贡献)
2. 子树内对子树外贡献

这样就把这个节点的贡献不重不漏地分成两部分，且都可以根据我们维护的信息快速得出。

1. 子树内相互贡献

对于第一部分，我们暴力合并轻子求解，算法流程如下：
1. 枚举子树\(map_s\)内的信息\((w,c_w)\),如果\(w < w_p\),将贡献\(c_w * map_p[c_w]\)(这里应该先count)计入该点的贡献。
2. 并入子树\(map_s\)内的信息。
3. 对下一轻子重复1，2.

需要注意的是(注意节点\(p\)的子树和它的子节点的子树的区别)
1. 我们不能边计算贡献边把轻子信息并入这个点。因为这样可能导致计算同一子节点的子树内的点的相互贡献，而同一子节点的子树内的点的路径不经过\(p\)。
2. 我们不能先把贡献全算一遍，在来加一遍信息。这样会导致只计算了轻子树对重子树的贡献，轻子树之间的贡献没有计算。

这两点对于理解子树内贡献的正确性是非常重要的。

1，2两步的复杂度均为\(O(size_s)\)(不考虑map的常数，实际上这里使用unorder_map完全没问题)。由重链剖分的复杂度分析，这部分的复杂度为\(O(n\log n)\)。

2.子树内对子树外贡献

在计算完第一部分的贡献后，我们合并了这个子树内的信息。于是可以尝试计算子树内对子树外的贡献。(不要推的时候把这部分贡献给搞漏了)
我们可以先预先统计整个树上\(w\)权值的点数\(t_s\)。那么知道了子树内权值为\(w\)的点数\(c_w\)，子树外权值为\(w\)的点数就相当好得到，一个简单的容斥告诉我们为\(t_w - c_w\)。
一个朴素的计算方法是，遍历这个点\(map\)上的所有权值\((w,c_w)\),计算出贡献和\(\sum_w c_w * (t_w - c_w) * [w < w_p]\)。
显然，这个是\(O(size_p)\)的，复杂度有问题。
我们要求的贡献是一个类似前缀和的东西(因为大于等于\(w_p\)的都被舍去了),考虑尝试使用树状数组维护。
我们考虑拆解贡献的计算式：
\[\sum_w c_w * (t_w - c_w) * [w < w_p] = \sum_w c_w*t_w - \sum c_w^2\]
我们可以使用两个树状数组分别维护\(c_w*t_w 、c_w^2\),求解一个点的贡献的复杂度就是求区间和，复杂度是\(O(\log n)\).那么第二部分的总复杂度为\(O(n \log n)\)
在维护树状数组对前面加入信息的影响。
并入信息的单点修改时间复杂度为\(O(\log n)\),每个点最多加入\(\log n\)次那么这部分是时间复杂度为\(O(n \log ^2 n)\)

总结

我们通过分别计算子树内相互贡献、子树内对子树外贡献，总的时间复杂度为\(O(n \log ^2n)\)

T2 CF1681F

~~dsu on tree 好难想，做的时候凑贡献式子wa了一上午~~

题目大意

\(n\)个点的树，有边权。
\(f(u,v) = u\)到\(v\)的路径上仅出现一次的边权数。
求\(\sum_u\sum_vf(u,v)\)

分析

虽然虚树，线段树分治什么的都可以做而且思维难度我感觉远小于dsu on tree，但是拿来练一练\(dsu on tree\)还是可以的。(~~就是太折磨了~~)
我们要维护的信息显然就是子树内的边权集(边权出现个数)，不过计算贡献成了难题。
由于我们要计算的是二元组\((u,v)\)的个数所以我们不用像上题那样算什么子树内对外，这样一是会重复，而是计算合法的\((u,v)\)个数需要一定的路径信息，这是没办法通过简单容斥得到的。
由于我们是启发式合并，在确定了根的情况下，每条边\(\{fa[u],u\}\)都唯一依赖于远离根的点\(u\)，所以我们可以把边权转移到点上。
先考虑合并过程中，子树内边权集的情况。
1. 继承重子\(hson\)，加入点权\(val_{hson}\)，计算贡献
2. 合并轻子\(s\),加入点权集\(valset_s\)和\(val_s\)，计算贡献
3. 递归

我们可以发现合并儿子时还要单独加入儿子的权值，所以不如在递归前加入自身权值(即使自身的点权不属于自己的子树内的边权集，但是贡献计算完毕了)。

仅维护边权集并不足以让我们有足够的信息计算出答案。我们需要维护新的信息，或者想想怎么计算贡献。

我们考虑两种操作分别的影响：
1. 继承重子(多了一个新的边)
2. 合并轻子(多了一个新的子树)

对于操作1，\(cover\)的更新为\(cover[w_{h}] = size(p)\)

先看操作1。
我们考虑新的点\(p\)到重子\(h\)内每个点的路径。重子点权为\(w\)
如果路径上没有相同边权，相对于原来从重子节点的路径，贡献多1。
反之如果有，贡献怎么变?。
仔细想想：如果路径上有1个相同边权，那么新路径和这条路径的贡献都变成0，相对于原贡献-1.这些点是什么呢？最浅层被\(w\)的点夹着的点(包括上面那个)
如果路径上有2个以上的相同边权，这些贡献已经清零了，相对于原贡献不变。这些点是剩余那些。
我们用\(cover\)(覆盖，很形象,可以是一个map)来记录在点权为\(w\)的子树内的点。
用\(between\)(中间，被\(w\)的夹着的点)来记录最浅层被\(w\)的点夹着的点(包括上面那个)的个数。
计从子树根出发的到子树内点的总贡献为\(val\)
贡献多-1的点数为\(between\)，贡献多0的点数为\(cover[w] - between[w]\),贡献多1的点数为\(size - cover[w]\)
那么，继承重子的贡献为:\(val[h] + size[h] - cover[w] - between[w]\)
我们不如在递归下一层前，用上式更新自己的\(val\)，所以新的\(val\)定义为添加一个不冲突的点，应该加上的贡献。

对于操作2，我们要求合并一个轻子\(s\)多出来的贡献。
首先由于我们要确保时间复杂度正确，我们只能枚举轻子的信息。
考虑将新的路径拆成2部分，一部分是在重子(包括已经合并完了的轻子)的路径，一部分是轻子那边的路径。
对于重子那边的路径，相当于加了\(sz_s\)个点(先不考虑边权问题)，贡献为\(val_p*size_s\),同理轻子那边的贡献为\(val_s*size_p\)。
再考虑冲突问题，哪些点会产生冲突减少贡献呢？
考虑一个轻子里(对)\(between[w]\)(有贡献)的点，路径上带有一个\(w\)，如果在重子那边遇到一个\(cover[w]\)的点，路径上就有2个\(w\)，所以在减去轻子这边多算的贡献时应该减去\(\sum_w between_s[w] \times cover_p [w]\)。
我们对偶地考虑，那么为了减去重子那边多算的贡献，我们减去\(\sum_w cover_s [w] \times between_p[w]\)
(我们只考虑边\(between\)的点的损失，这样就不重不漏)

最后我们考虑加点更新信息。
首先目前我们加点(实际上是加边)，首先是加入其他子树，最后才是加入自身。(想一想边集变化，上面也有解释)。
操作2的影响是很直接的，\(cover\)和\(between\)直接按点值加就行，没有相互作用。
操作完后加入自身，\(cover[w_p] = size[p], between[p] = cover[p] - precover[w_p]\)，所以我们先修改\(between\),再修改\(cover\)。

再理一下算法流程：
1. 继承重子，加上贡献\(val[p]\)
2. 遍历轻子并且合并，加上贡献
3. 加入自身，修改自身的\(val 、cover 、between\)

考虑map的复杂度，时间复杂度为\(O(n \log^2 n)\)。
以下是我变量命名一塌糊涂的代码

#include<bits/stdc++.h>

using ll = long long;
using ull = unsigned long long;
using i64 = long long;

using namespace std;


void solve()
{
    using edge = pair<int, int>;
    int n;
    cin >> n;
    vector<vector<edge>>g(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    vector<int>fa(n + 1, -1), hson(n + 1, -1), sz(n + 1, 1), w(n + 1);
    function<void(int)>dfs = [&](int p)->void
        {
            for (auto& [s, wi] : g[p]) {
                if (s != fa[p]) {
                    fa[s] = p;
                    w[s] = wi;
                    dfs(s);
                    sz[p] += sz[s];
                    if (hson[p] == -1 || sz[hson[p]] < sz[s]) {
                        hson[p] = s;
                    }
                }
            }
            return;
        };

    vector<int>cnt2(n + 1);
    vector<ll>val(n + 1);
    vector<int>newsz(n + 1, 1);

    
    ll ans = 0;

    auto merge = [&](int fa, int p)
        {
            val[fa] += val[p];
            newsz[fa] += newsz[p];
        };

    //mp : \sum dep*cnt  cnt: 覆盖点数
    function<void(int, map<int, ll>& cnt, map<int, ll>& cnt2)>dsu = [&](int p, map<int, ll>& cnt, map<int,ll>&cnt2 )->void
        {
            if (hson[p] != -1) {
                dsu(hson[p], cnt, cnt2);
                //合并hson
                ans += val[hson[p]];
                merge(p, hson[p]);

                for (auto& [s, w] : g[p]) {
                    map<int, ll>tmp2,tmp3;
                    if (s != hson[p] && s != fa[p]) {
                        dsu(s,tmp2, tmp3);
                        ans += val[p] * newsz[s] + val[s] * newsz[p];

                        //p to lson
                        for (auto& [v, c] : tmp3) {
                            ans -= c * cnt[v];
                            //mp[v] += c;
                        }

                        //lson to p
                        for (auto& [v, c] : tmp2) {
                            ans -= c * cnt2[v];
                            cnt[v] += c;
                        }

                        for (auto& [v, c] : tmp3) {
                            //ans -= c * mp[v];
                            cnt2[v] += c;
                        }
                        merge(p, s);
                    }
                }

            }

            //add p self
            val[p] += sz[p];
            val[p] -= cnt[w[p]] + cnt2[w[p]];
            
            cnt2[w[p]] = sz[p] - cnt[w[p]];
            cnt[w[p]] = sz[p];
            
        };

    map<int, ll>tmp,tmp2,tmp3;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    int root = rng() % n + 1;
    //root = 1;
    dfs(root);
    dsu(root,tmp2, tmp3);
    cout << ans << endl;
    return;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
   
        solve();
    return 0;
}