一.简介
其实点差分和边差分区别不大。
点差分中，d数组存储的是树上的节点
边差分中，d数组存储的是当前节点到父节点的那条边的差分值。
指定注意的是：边差分中因为根连的父节点是虚点，所以遍历结果时应当忽略！
二.题目
样例输入：
4 1
1 2
2 3
1 4
3 4样例输出：3
三.题目分析
我们易知：
加上一条边时，相当于把所经过的节点都加了一条命。（这时用差分快一些）
（为了方便，我们令边的权值为-1时，才算断掉）
若一条边最后还是没加命，即0；所以切断它，图就不连通了，所以红边任意切一条即可。所以此边贡献为m；
若这条边有一条命，我们切断它后，它还有一条命，固只能再切掉给它续命的那条红边，图才不联通，所以此边贡献为1；文章来源：https://www.toymoban.com/news/detail-620235.html
若这条边有2条以及以上条命，我们显然要切3次及三次以上。但我们只能切二次。它命太硬了，所以我们放弃这条边。次边贡献为0；文章来源地址https://www.toymoban.com/news/detail-620235.html
四.参考代码
/*
4 1
1 2
2 3
1 4
3 4
*/
#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
struct Edge{
int u,v,next;
}edge[maxn<<1];
int head[maxn],cnt=0;
void add(int u,int v){
edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
int depth[maxn],p[maxn][30],d[maxn];
void dfs1(int u,int fa){
depth[u]=depth[fa]+1;
p[u][0]=fa;
for(int i=1;(1<<i)<=depth[u];i++){
p[u][i]=p[p[u][i-1]][i-1];
}
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(fa!=v) dfs1(v,u);
}
}
int LCA(int x,int y){
if(depth[x]<depth[y]) swap(x,y);
int lg=0;
while((1<<lg)<=depth[x]) lg++;
for(int i=lg;i>=0;i--){
if(depth[x]-(1<<i)>=depth[y]){
x=p[x][i];
}
}
if(x==y) return x;
for(int i=lg;i>=0;i--){
if(p[x][i]!=p[y][i]){
x=p[x][i]; y=p[y][i];
}
}
return p[x][0];
}
void dfs2(int u,int fa){
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(v!=fa){
dfs2(v,u);
d[u]+=d[v];
}
}
}
int main(){
//读入数据
scanf("%d%d",&n,&m);
int u,v;
for(int i=1;i<n;i++){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
//建树
dfs1(1,0);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
d[u]++; d[v]++;
int lca=LCA(u,v);
d[lca]-=2;
}
//sum原数组
dfs2(1,0);
int ans=0;
//i从2开始，因为1连的父节点是虚点
for(int i=2;i<=n;i++){
if(d[i]==0) ans+=m;
else if(d[i]==1) ans++;
}
cout<<ans;
return 0;
}到了这里，关于【图论】树上差分（边差分）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
