E. Number of Simple Paths

解题思路：这题主要考察了两个知识点。在一个n个点n条边的树中路径有n*(n-1)个。在n个点n-1条边的树中路径有n*(n-1)/2个。这题先求出总共的路径ans，将环看作是一个点a，用ans-以a为顶点的子树中的路径。

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double lf; typedef pair<int,int>P; const int inf = 0x7f7f7f7f; const int N = 2e5+10; const ll mod = 20000311; const double PI = 3.14;  int read(){     char ch=getchar();int x=0,f=1;     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}     while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}     return x*f; } int random(int n){return(ll)rand()*rand()%n;}  vector<int>G[N]; int vis[N],d[N];  ll cnt = 0;  void dfs(int u){     for(int i = 0;i < G[u].size();i++){         int v = G[u][i];         if(vis[v]) continue;         vis[v] = 1;         cnt++;         dfs(v);     } } void solve(){     int n = read();     for(int i = 1;i <= n;i++){         G[i].clear();vis[i] = 1;d[i] = 0;     }     for(int i = 1;i <= n;i++){         int u = read(),v = read();         G[u].push_back(v);         G[v].push_back(u);         d[u]++;d[v]++;     }     queue<int>que;     for(int i = 1;i <= n;i++){         if(d[i] == 1) que.push(i);     }     while(que.size()){         int u = que.front();que.pop();         if(vis[u] == 0) continue;         vis[u] = 0;         for(int i = 0;i < G[u].size();i++){             int v = G[u][i];             if(d[v] >= 2 && vis[v] == 1){                 d[v]--;                 if(d[v] == 1) que.push(v);             }         }     }      ll ans = (ll)n*(n-1);     for(int i = 1;i <= n;i++){         if(vis[i]){             cnt = 1;             dfs(i);             ans -= cnt*(cnt-1)/2;         }     }     cout<<ans<<endl;  } int main(){     srand((unsigned)time(0));     //freopen("out.txt","w",stdout);     //freopen("in.txt","r",stdin);     int t = read();     while(t--){         solve();     }     return 0; }  

c/c++开发分享E. Number of Simple Paths地址：https://blog.csdn.net/weixin_42868863/article/details/110205447