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.
#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;
}