abc378F
作者:
Air1222
,
2024-11-13 21:46:44
,
所有人可见
,
阅读 2
//最简单的一道F
//1.找度数为3的连通块
//2.统计与度数为3的连通块连接的节点的个数
//3.ans=cnt*(cnt-1)/2
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5+10;
typedef long long LL;
int n;
vector<int>g[N];
int d[N];
bool st[N];
LL ans;
LL cnt;
void dfs(int u)
{
st[u]=true;
for(auto k:g[u])
{
if(st[u]) continue;
if(d[k]==3) dfs(k);
}
}
void dfs1(int u)
{
st[u]=false;
for(auto k:g[u])
{
//cout<<u<<" "<<k<<endl;
if(d[k]==2) cnt++;
if(!st[k]) continue;
dfs1(k);
}
}
int main()
{
cin>>n;
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
d[a]++;
d[b]++;
}
for(int i=1;i<=n;i++)
if(d[i]==3&&!st[i])
dfs(i);
for(int i=1;i<=n;i++)
if(st[i])
{
cnt=0;
dfs1(i);
ans+=cnt*(cnt-1)/2;
}
cout<<ans;
return 0;
}