题目传送门：POJ - 3417 Network
题目大意：
存在一棵n个结点的树，加入m条新边，现在要让这个图不连通，你可以切断两条边，要求切断一条原边，一条新边，求切割的方案数。
分析：
加入m条新边，假设加入新边(u,v),那么u-->lca(u,v)-->v-->u形成一个环，此时可以切断新边，和环上任意的一条原边就可以使图不连通。
可以发现若加入一条新边，给环上的计数1，表示该边被一个环覆盖，树上有些边会被多个环覆盖，此时可以分情况讨论。
1、若该边被覆盖次数是0，则断掉该边后图已经满足不连通条件了，此时可以断掉任意一条新边，图依旧不连通，可该边以产生m种新方案。
2、若该边被覆盖次数是1，则断掉该边后必须断掉与之对应的新边才能使图不连通，可以产生1种新方案。
3、若该边被覆盖次数大于等于2，则不能在断掉一条新边和一条原边的情况下使图不连通，所以不能产生新方案。
所以该题目可以转化为，每次加入新边后，给形成对应的环上的边+1，最后统计树上所有边的权值（树上差分），若权值是0方案数+m，权值是1方案数+1
可以求出最后结果
代码
#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int MAX=100009;const int M=20;int n,m,a,b;int head[MAX],cnt=0;int up[MAX][M];int deep[MAX];int de[MAX];struct edge{ ???int next,to;}edge[MAX*2];inline void add(int u,int v){ ???edge[cnt].to=v; ???edge[cnt].next=head[u]; ???head[u]=cnt++;} ???void dfs(int u) ???????????????????????????????????????????????????//遍历数，求出结点的深度和父亲 { ???????????????for(int i=head[u];i!=-1;i=edge[i].next) ???????????????????{ ???????int to=edge[i].to; ???????if(to==up[u][0])continue; ???????deep[to]=deep[u]+1; ???????up[to][0]=u; ???????dfs(to); ???}}void init(){ ???memset(up,-1,sizeof(up)); ???deep[1]=1; ???dfs(1); ???for(int j=1;(1<<j)<=n;j++) ???????????????????????????????????//倍增 ????????for(int i=1;i<=n;i++) ???????????if(~up[i][j-1]) ???????????????up[i][j]=up[up[i][j-1]][j-1];}int lca(int a,int b){ ???if(deep[a]<deep[b]) ???????swap(a,b); ???int d=deep[a]-deep[b]; ???for(int i=0;i<M;i++) ???????if(d&(1<<i)) ???????????a=up[a][i]; ???????if(a==b)return a; ???for(int i=M-1;i>=0;i--) ???{ ???????if(up[a][i]!=up[b][i]) ???????????a=up[a][i],b=up[b][i]; ???} ???return up[a][0];}void dfs_ans(int u) ????????????????????????????????????????????????{ ???for(int i=head[u];i!=-1;i=edge[i].next) ???{ ???????int to=edge[i].to; ???????if(to==up[u][0])break; ????????dfs_ans(to); ???????de[u]=de[u]+de[to]; ???????}}int main(){ ???memset(head,-1,sizeof(head)); ???memset(de,0,sizeof(de)); ???scanf("%d%d",&n,&m); ???for(int i=1;i<n;i++) ???{ ???????scanf("%d%d",&a,&b); ???????add(a,b); ???????add(b,a); ???} ???init(); ???for(int i=0;i<m;i++) ???{ ???????scanf("%d%d",&a,&b); ???????de[a]++; ???????????????????????????????//树上差分 ????????de[b]++; ???????de[lca(a,b)]-=2; ???} ???dfs_ans(1); ???int res=0; ???for(int i=2;i<=n;i++) ????????????????????????????{ ???????if(de[i]==0) ???????????res+=m; ???????if(de[i]==1) ???????????res++; ???} ???printf("%d\n",res); ???return 0;} POJ - 3417 Network (LCA+树上差分)
原文地址：https://www.cnblogs.com/LjwCarrot/p/9738045.html