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;
}

本文地址：https://blog.csdn.net/weixin_42868863/article/details/110205447