Editorial for Trees and Criticality
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
#include <bits/stdc++.h>
using namespace std;
bool *explored;
int *componentCounts;
vector<int> *adjList;
int dfs(int node) {
int componentCount = 0;
for (auto i : adjList[node])
if (!explored[i])
{
explored[i] = true;
componentCount += dfs(i);
}
componentCount++;
return componentCounts[node] = componentCount;
}
int main() {
int n;
cin >> n;
adjList = new vector<int>[n];
for (int i = 0; i < n - 1; i++)
{
int f, t;
cin >> f >> t;
f--, t--;
adjList[t].emplace_back(f);
adjList[f].emplace_back(t);
}
explored = new bool[n], componentCounts = new int[n];
memset(explored, 0, n * sizeof(bool));
explored[0] = true;
dfs(0);
long long result = 0;
for (int node = 0; node < n; node++)
{
long long criticality = 1ll;
for (auto neighbour : adjList[node])
if (componentCounts[neighbour] < componentCounts[node])
criticality *= componentCounts[neighbour];
else
criticality *= componentCounts[0] - componentCounts[node];
result = max(result, criticality);
}
cout << result << '\n';
// cout << result << endl;
return 0;
}