题目：http://poj.org/problem?id=3417
根据一条边被几个环覆盖来判断能不能删、有几种情况等；
用树上差分，终点 s++，LCA s-=2，统计时计算子树s值的和即可；
用ST表做LCA，不知为何WA了，于是改成了tarjan，过程中求答案；
注意非树边加边时判掉x=y的情况。
代码如下：
#include<iostream>#include<cstdio>#include<cstring>using namespace std;int const MAXN=1e5+5;int n,m,head[MAXN],ct,s[MAXN],fa[MAXN],ct2,head2[MAXN];long long ans;bool vis[MAXN];struct N{ ???int to,next; ???N(int t=0,int n=0):to(t),next(n) {}}edge[MAXN<<1],ed[MAXN<<1];int find(int x) ?{ ?????if(fa[x]==x)return x; ?????return fa[x]=find(fa[x]); ?} ?void tarjan(int x) ?{ ?????fa[x]=x;vis[x]=1; ???for(int i=head2[x],u;i;i=ed[i].next) ???????if(vis[u=ed[i].to])s[find(u)]-=2; ???for(int i=head[x],u;i;i=edge[i].next) ???{ ???????if(vis[u=edge[i].to])continue;//fa ???????tarjan(u);fa[u]=x;s[x]+=s[u]; ???????if(s[u]==0)ans+=m; ???????if(s[u]==1)ans++; ???}} ?int main(){ ???scanf("%d%d",&n,&m); ???for(int i=1,x,y;i<n;i++) ???{ ???????scanf("%d%d",&x,&y); ???????edge[++ct]=N(y,head[x]);head[x]=ct; ???????edge[++ct]=N(x,head[y]);head[y]=ct; ???} ???for(int i=1,x,y;i<=m;i++) ???{ ???????scanf("%d%d",&x,&y); ???????if(x==y)continue;//! ???????s[x]++;s[y]++; ???????ed[++ct2]=N(y,head2[x]);head2[x]=ct2; ???????ed[++ct2]=N(x,head2[y]);head2[y]=ct2; ???} ???tarjan(1); ???printf("%d",ans); ???return 0;}poj3417 Network——LCA+树上差分
原文地址：https://www.cnblogs.com/Zinn/p/8932947.html