ABC378

F - Add One Edge 2

题意：一颗有n个顶点的树，第i条边双向连接顶点ui和vi，在给定的树上添加一条不定向边，总能得到一个正好有一个循环的图。在这些图中，有多少个满足所有顶点都有阶数3

分析：每次阶数为3的dfs找阶数为2的个数，两个阶数为2的即可凑出循环图，所以满足条件的个数为cnt*(cnt-1)/2

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N=2e5+10;
vector<int>G[N];
int n;
int deg[N];
bool vis[N];
int cnt=0;
ll ans=0;
void dfs(int v,int fa=0){//无父节点 fa=0作初始值if(deg[v] != 3){//由于作为可连接的点 可能连接了多个联通块不打标记cnt += (deg[v]==2);return;}vis[v] = 1;for(auto x:G[v]){//x是节点v相连的if(x == fa) continue;dfs(x,v);}
}
void sol(){cin>>n;for(int i = 1;i < n;++i){int u,v;cin>>u>>v;G[u].push_back(v);G[v].push_back(u);++deg[u];++deg[v];}for(int i=1;i<=n;++i){// 找 deg=3 的连通块if(deg[i] != 3) continue;if(vis[i]) continue;cnt = 0;dfs(i);ans += cnt*(cnt-1)/2;}cout<<ans<<"\n";    
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t;t=1;for(int i=1;i<=t;i++)sol();return 0;
}
​