假设是一棵树,答案是n*(n-1)/2
这是因为任意两点间的路只有一条。
如果全部点都在一个环上,那么答案是n*(n-1),因为任意两点都有两种情况
在考虑两个极端的情况,我们可以发现,主要的变数就是通过了环,任何两个能够通过环到达的点都是存在两条路径的
因此,我们考虑环上每个点的子树大小,这下面的点因为不能通过环,所以只有一个简单路径
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=6e5+10; const int mod=998244353; int h[N],ne[N],e[N],idx; int ins[N],fu[N]; int st[N]; vector<int> num; ll sz[N]; void add(int a,int b){ e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void dfs(int u,int from){ int i; ins[u]=1; for(i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(i==(from^1)) continue; fu[j]=u; if(ins[j]){ int x=u; while(x!=j){ num.push_back(x); x=fu[x]; } num.push_back(j); } else{ dfs(j,i); } } ins[u]=0; } void dfs1(int u,int fa){ sz[u]=1; for(int i=h[u];i!=-1;i=ne[i]){ int j=e[i]; if(st[j]) continue; if(j==fa) continue; dfs1(j,u); sz[u]+=sz[j]; } } int main(){ ios::sync_with_stdio(false); memset(h,-1,sizeof h); int t; cin>>t; while(t--){ ll n; cin>>n; int i; idx=0; num.clear(); for(i=1;i<=n;i++){ h[i]=-1; st[i]=0; } for(i=1;i<=n;i++){ int a,b; cin>>a>>b; add(a,b); add(b,a); } dfs(1,-1); for(i=0;i<num.size();i++){ st[num[i]]=1; } ll ans=n*(n-1); for(i=1;i<=n;i++){ if(st[i]){ dfs1(i,0); ans-=(sz[i]*(sz[i]-1))/2; } } cout<<ans<<endl; } return 0; }View Code