思路：
考虑加入新边对原图的影响：
每加入一条边，相当于在原图中构成一个环，因此要使原图在这个环上断开，必须删去这条新边和环上任意一条树边。
统计每一条树边出现在多少个环中，计作$c$：
1.$c=0$，则该边不属于任何一个环，因此删去这条边的同时删去任意一条新边即可，对答案的贡献是$m$；
2.$c=1$，则该边仅属于一个环，因此删去这条边并删去该环上的新边即可，对答案的贡献是$1$；
3.$c\geq 2$，则该边同时包含于多个环中，无论删去哪一个新边，总有别的环使原图连通，对答案的贡献是$0$。
因此我们可以统计$c$来得到答案。
我们可以利用树上差分的思想，对于每条新边$(u,v)$，$f_u=f_u+1$，$f_v=f_v+1$，$f_{LCA(u,v)}=f_{LCA(u,v)}+1$。
最后用树形DP求出每条边被环包含的次数。
Tarjan求LCA。
但是在OJ上测会TLE，必须要把vector改成前向星才可以。
1 #include<cstdio> 2 #include<cctype> 3 inline int getint() { 4 ????char ch; 5 ????while(!isdigit(ch=getchar())); 6 ????int x=ch^‘0‘; 7 ????while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^‘0‘); 8 ????return x; 9 }10 const int root=1,nil=0;11 const int V=100001;12 struct Edge {13 ????int to,next;14 };15 int sz=0;16 Edge edge[V<<2];17 int e[V]={0},q[V]={0};18 inline void add_edge(const int u,const int v) {19 ????edge[++sz]=(Edge){v,e[u]};20 ????e[u]=sz;21 }22 inline void add_query(const int u,const int v) {23 ????edge[++sz]=(Edge){v,q[u]};24 ????q[u]=sz;25 }26 class DisjointSet {27 ????private:28 ????????int anc[V];29 ????public:30 ????????DisjointSet() {31 ????????????for(int i=0;i<V;i++) anc[i]=i;32 ????????}33 ????????int Find(const int x) {34 ????????????return x==anc[x]?x:anc[x]=Find(anc[x]);35 ????????}36 ????????void Union(const int x,const int y) {37 ????????????anc[Find(x)]=Find(y);38 ????????}39 };40 DisjointSet s;41 bool vis[V]={0};42 int f[V]={0};43 void Tarjan(const int x,const int par) {44 ????for(int i=e[x];i;i=edge[i].next) {45 ????????int &y=edge[i].to;46 ????????if(y!=par) Tarjan(y,x);47 ????}48 ????for(int i=q[x];i;i=edge[i].next) {49 ????????int &y=edge[i].to;50 ????????if(!vis[y]) continue;51 ????????int lca=s.Find(y);52 ????????f[x]++,f[y]++,f[lca]-=2;53 ????}54 ????s.Union(x,par);55 ????vis[x]=true;56 }57 int cnt[2]={-1};58 void DP(const int x,const int par) {59 ????for(int i=e[x];i;i=edge[i].next) {60 ????????int &y=edge[i].to;61 ????????if(y==par) continue;62 ????????DP(y,x);63 ????????f[x]+=f[y];64 ????}65 ????if(f[x]<2) cnt[f[x]]++;66 }67 int main() {68 ????int n=getint(),m=getint();69 ????for(int i=1;i<n;i++) {70 ????????int u=getint(),v=getint();71 ????????add_edge(u,v);72 ????????add_edge(v,u);73 ????}74 ????for(int i=1;i<=m;i++) {75 ????????int u=getint(),v=getint();76 ????????add_query(u,v);77 ????????add_query(v,u);78 ????}79 ????Tarjan(root,nil);80 ????DP(root,nil);81 ????printf("%d\n",cnt[0]*m+cnt[1]);82 ????return 0;83 }[POJ3417]Network
原文地址：http://www.cnblogs.com/skylee03/p/7435044.html