Submission #2869906

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

void calc_depths(vvi &tree, int loc, int par, int dep, vi &mc) {
    int nc = 0;
    for (int nbr : tree[loc]) {
        if (nbr != par) {
            nc++;
            calc_depths(tree, nbr, loc, dep+1, mc);
        }
    }

    if (nc) {
        while (mc.size() <= dep) mc.push_back(0);
        mc[dep] = max(mc[dep], nc);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    int N;
    cin >> N;

    vvi tree(N);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        tree[u-1].push_back(v-1);
        tree[v-1].push_back(u-1);
    }

    int md = INT_MAX;
    vvi depths(N);
    for (int i = 0; i < N; i++) {
        calc_depths(tree, i, i, 0, depths[i]);
        md = min(md, (int) depths[i].size());
    }

    vi centers;
    for (int i = 0; i < N; i++) {
        if (depths[i].size() == md)
            centers.push_back(i);
    }

    if (centers.size() == 2) {
        vi mc1; calc_depths(tree, centers[0], centers[1], 0, mc1);
        vi mc2; calc_depths(tree, centers[1], centers[0], 0, mc2);
        ll ans = 2;
        for (int i = 0; i < mc1.size(); i++)
            ans = ans * max(mc1[i], mc2[i]);
        cout << mc1.size() + 1 << " " << ans << endl;
        return 0;
    }

    // case that we just use the center as the root
    vi mc; calc_depths(tree, centers[0], centers[0], 0, mc);
    int col = mc.size() + 1;
    ll ans = 1; for (int v : mc) ans *= v;

    // try making a neighbor the second center
    for (int nbr : tree[centers[0]]) {
        vi mc1; calc_depths(tree, centers[0], nbr, 0, mc1);
        vi mc2; calc_depths(tree, nbr, centers[0], 0, mc2);
        while (mc1.size() < mc2.size()) mc1.push_back(0);
        while (mc2.size() < mc1.size()) mc2.push_back(0);
        ll cand = 2;
        for (int i = 0; i < mc1.size(); i++)
            cand *= max(mc1[i], mc2[i]);
        if (mc1.size() + 1 < col) {
            col = mc1.size() + 1;
            ans = cand;
        } else if (mc1.size() + 1 == col) {
            ans = min(ans, cand);
        }
    }

    cout << col << " " << ans << endl;
    return 0;
}

Submission Info

Judge Result