思路：
可以发现题目就是要我们找出有多少个点对满足连成后是一个简单环
环上的点度都为3
因为是一个简单图
所以不可以有重边和自环
那么就代表着这个环肯定是由两个度为2的点和大于1个度为3的点组成的
注意到两个点的最近公共祖先一定可以跟这两个点形成环
所以我们用一个度为3的点去找
只往度为3的结点走
找到的所有度为2的点都可以彼此连成环
就像这样
红点之间都可以彼此连成环
答案就是
由于每个点最多只被遍历一次
所以时间复杂度是的
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,sum,ans;
vector<int>a[210000];
bool vis[210000];
void dfs(int x,int fa)
{
vis[x]=1;
for(int i=0;i<a[x].size();++i)
{
if(a[x][i]==fa)
{
continue;
}
if(a[a[x][i]].size()==2)
{
sum++;
}
else if(a[a[x][i]].size()==3)
{
dfs(a[x][i],x);
}
}
}
signed main()
{
scanf("%lld",&n);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%lld%lld",&x,&y);
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(a[i].size()==3&&!vis[i])
{
sum=0;
dfs(i,0);
ans=ans+sum*(sum-1)/2;
}
}
printf("%lld",ans);
return 0;
}记住要开long long
标签：AtCoder,连成,210000,int,题解,度为,vis,long,378 From： https://blog.csdn.net/m0_60355267/article/details/143461356