这道题挺妙的,说到底还是自己的思维不行啊....
首先我们在拿到题目时,要深刻的对模型之类的东西进行运用...
一个树,加上m个非树边,第一次割掉树边,第二次割掉非树边,使得整个图不连通.问有多少个方案.
我们考虑一个树,加上一个边(x,y)。那x,y之间的路径加上这条边就形成一个环.
对于(x,y)之间的树边而言,如果我们割掉任何一条边,整个图仍是联通的.所以我们下一步必须割掉链接x，y的非树边才能使得这个图不连通
所以我们将x到y的路径上的边都加1.意思是割掉这些边后必须割掉一条边才能使得整个图不连通.
我们对所有的非树边都这样做,对于一条边,他会有一个数值x,意思是割掉这条边后,必须割掉x条边才能使得整个图不连通.
当然可能存在值为0的边,意思是割掉他后图就不连通..
这样之后我们要求方案树就容易多了...
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=100010; int n,m,link[N],c[N],tot,f[N][25],deep[N],ans; struct edge{int y,next;}a[N<<1]; inline int read() { int x=0,ff=1; char ch=getchar(); while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();} while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*ff; } inline void add(int x,int y) { a[++tot].y=y;a[tot].next=link[x];link[x]=tot; a[++tot].y=x;a[tot].next=link[y];link[y]=tot; } inline void bfs() { queue<int>q;q.push(1); deep[1]=1; while(!q.empty()) { int x=q.front();q.pop(); for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(deep[y]) continue; deep[y]=deep[x]+1; q.push(y); f[y][0]=x; for(int j=1;j<=20;++j) f[y][j]=f[f[y][j-1]][j-1]; } } } inline int lca(int a,int b) { if(deep[a]>deep[b]) swap(a,b); for(int i=20;i>=0;--i) if(deep[f[b][i]]>=deep[a]) b=f[b][i]; if(a==b) return a; for(int i=20;i>=0;--i) if(f[b][i]!=f[a][i]) a=f[a][i],b=f[b][i]; return f[a][0]; } inline void dfs(int x) { for(int i=link[x];i;i=a[i].next) { int y=a[i].y; if(y==f[x][0]) continue; dfs(y); c[x]+=c[y]; } if(c[x]==1) ans++; else if(c[x]==0) ans+=m; } int main() { //freopen("1.in","r",stdin); n=read();m=read(); for(int i=1;i<n;++i) { int x=read(),y=read(); add(x,y); } bfs(); for(int i=1;i<=m;++i) { int x=read(),y=read(); int o=lca(x,y); c[x]++;c[y]++;c[o]-=2; } dfs(1); printf("%d",ans); return 0; }