【图论】树上差分（边差分）

一.简介

其实点差分和边差分区别不大。

点差分中，d数组存储的是树上的节点

边差分中，d数组存储的是当前节点到父节点的那条边的差分值。

指定注意的是：边差分中因为根连的父节点是虚点，所以遍历结果时应当忽略！ 

 

---

二.题目 

 

 样例输入：

4 1
1 2
2 3
1 4
3 4

样例输出：3

三.题目分析 

我们易知：

加上一条边时，相当于把所经过的节点都加了一条命。（这时用差分快一些）

（为了方便，我们令边的权值为-1时，才算断掉）

若一条边最后还是没加命，即0；所以切断它，图就不连通了，所以红边任意切一条即可。所以此边贡献为m；

若这条边有一条命，我们切断它后，它还有一条命，固只能再切掉给它续命的那条红边，图才不联通，所以此边贡献为1；

若这条边有2条以及以上条命，我们显然要切3次及三次以上。但我们只能切二次。它命太硬了，所以我们放弃这条边。次边贡献为0；

---

四.参考代码

/*
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;
}