Solution in c++
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
int pai=0,avo,tar;
lli n,f,b,t1,t2,be,fl;
vector<int>adj[300009];
queue<int> tur;
int vis[300009];
int dfs(int x)
{
if(vis[x])return 0;
vis[x]++;
if(x==tar)pai= 1;
for(auto u : adj[x])
{
if(u!=avo)dfs(u);
}
vis[x]=0;
return 0;
}
int cnt(int x)
{
int cou=1;
while(!tur.empty())
{
int t=tur.front();
tur.pop();
if(vis[t])continue;
vis[t]++;
for(auto u : adj[t])
{
if(vis[u] )continue;
tur.push(u);
cou++;
}
}
return cou;
}
int main()
{
cin>>n>>f>>b;
for(int i=0;i<n-1;i++)
{
cin>>t1>>t2;
adj[t1].push_back(t2);
adj[t2].push_back(t1);
}
for(auto u : adj[b])
{
avo=b;pai=0;
tar=f;dfs(u);
if(pai==1)
{
vis[u]=1;
tur.push(b);be=cnt(b);
break;
}
}
for(int i=1;i<=n;i++)vis[i]=0;
for(auto u : adj[f])
{
avo=f;pai=0;
tar=b;dfs(u);
if(pai==1)
{
vis[u]=1;
tur.push(f);fl=cnt(f);
break;
}
}
cout<< (n*(n-1) )-(be*fl);
return 0;
}
0 التعليقات:
إرسال تعليق