Kod: Zaznacz cały
#include <iostream>
#include<vector.h>
enum COLOR {WHITE, GREY, BLACK};
namespace X
{
vector<COLOR> color;
}
using namespace std;
int DFS_visit( vector< vector<int> > &Adj, vector<int> &d, vector<int> &pi, int u);
int max(int x, int y);
//---------------------------------------------------------------------------
int main()
{
ios_base::sync_with_stdio(0);
int n;
cin>>n;
vector< vector<int> > Adj(n);
vector<int> d(n, 1);
vector<int> pi(n, -1);
int a,b;
for(int i(0); i<n-1; ++i)
{
cin>>a>>b;
Adj[a-1].push_back(b-1);
Adj[b-1].push_back(a-1);
}
X::color.resize(n);
for(int i(0); i<n; ++i)
X::color[i]=WHITE;
for(int i(0); i<Adj[0].size(); ++i)
d[0]+=DFS_visit(Adj, d ,pi, Adj[0][i]);
int maximum(n-1);
for(int i(1); i<n; ++i)
{
//badanie krawedzi (i,pi[i])
maximum=max(maximum, d[i]*(n-d[i]));
}
cout<<maximum;
return(0);
}
//---------------------------------------------------------------------------
/*
0,1,2,...,n-1 - wierzcholki grafu
Adj-listy sąsiedztwa
d-ilosc potomków +1
pi-przodek w drzewie przeszukiwania w glab
*/
//u-wierzcholek poczatkowy
int DFS_visit( vector< vector<int> > &Adj, vector<int> &d, vector<int> &pi, int u)
{
X::color[u]=GREY;
for(int j(0); j<Adj[u].size(); ++j)
{
if(X::color[Adj[u][j]]==WHITE)
{
pi[Adj[u][j]]=u;
d[u]+=DFS_visit(Adj, d, pi, Adj[u][j]);
}
}
X::color[u]=BLACK; //wierzcholek zostal przetworzony
return(d[u]);
}
//-------------------------------------------------------------------
int max(int x, int y)
{
if(x>=y) return(x);
else return(y);
}