树上差分

主要是处理两种操作

1.找每条边被所有路径覆盖的次数

2.找每个点被所有路径覆盖的次数

这个东西还是非常实用的，记一下基本操作就行，其实就是前缀和思想，边/点的次数加上所有子节点的次数就是最终次数

点差分板子
神题 边差分+二分

找每条边被所有路径覆盖的次数

• 首先对已知的这 n 条路径的 起点a 和 终点b 的权值 +1 ，并对 lca(a, b) 的权值 -2 。
• 从根节点开始深搜，回溯时将其本身的权值加上所有子节点的权值。

void Add_cf(int x)
{
    sum[s[x]]++;sum[t[x]]++;sum[lc[x]]-=2;
}

void dfs3(int x)
{
    for(int i=head[x];i!=-1;i=edge[i].nt)
    {
        int v=edge[i].to;
        if(v==fa[x])continue;
        dfs3(v);
        sum[x]+=sum[v];

    }
}

找每个点被所有路径覆盖的次数

• 对每条路径的 起点a和终点b 的权值 +1 , 对 lca(a, b) 的权值 -1 , 对 lca(a, b)的父节点 权值 -1
• 从根节点开始深搜，回溯时将其本身的权值加上所有子节点的权值
• 每个节点的权值既是其被路径覆盖的次数

void Add_cf(int x)
{
    sum[a[x]]++;sum[a[x+1]]++;
    int LCA=lca(a[x],a[x+1]);
    sum[LCA]--;sum[fa[LCA]]--;

}

dfs过程没有任何区别