树上差分
主要是处理两种操作
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过程没有任何区别