Submission #947407

#	Time	Username	Problem	Language	Result	Execution time	Memory
947407		Pring	Hard route (IZhO17_road)	C++17	52 / 100	298 ms	1372 KiB

road

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

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 5005;
int n;
vector<int> edge[MXN];
pii dp[MXN][2];

struct STACK {
    vector<int> v;
    void init() {
        v.clear();
        v.push_back(0);
    }
    void push(int x) {
        v.push_back(max(v.back(), x));
    }
    void pop() {
        v.pop_back();
    }
    int get() {
        return v.back();
    }
} st;

pii operator+(pii a, pii b) {
    if (a < b) swap(a, b);
    if (a.fs == b.fs) a.sc += b.sc;
    return a;
}

pii &operator+=(pii &a, pii b) {
    return (a = a + b);
}

void push_pii(int id, pii p) {
    if (p > dp[id][0]) {
        dp[id][1] = dp[id][0];
        dp[id][0] = p;
    } else dp[id][1] = max(dp[id][1], p);
}

void DFS_PRE(int id, int par) {
    dp[id][0] = mp(0LL, 0LL);
    dp[id][1] = mp(0LL, 0LL);
    for (auto &i : edge[id]) {
        if (i == par) continue;
        DFS_PRE(i, id);
        push_pii(id, mp(1 + dp[i][0].fs, i));
    }
}

void DFS(int id, int par, int dep, pii &ans) {
    if (edge[id].size() == 1) {
        ans = ans + mp(dep * st.get(), 1LL);
        return;
    }
    st.push(dp[id][1].fs);
    DFS(dp[id][0].sc, id, dep + 1, ans);
    st.pop();
    st.push(dp[id][0].fs);
    for (auto &i : edge[id]) {
        if (i == par) continue;
        if (i == dp[id][0].sc) continue;
        DFS(i, id, dep + 1, ans);
    }
    st.pop();
}

pii solve(int rt) {
    DFS_PRE(rt, 0);
    st.init();
    pii ans = mp(0LL, 0LL);
    for (auto &i : edge[rt]) {
        DFS(i, rt, 1, ans);
    }
    return ans;
}

void miku() {
    int x, y;
    cin >> n;
    FOR(i, 1, n) {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    pii ans = mp(0LL, 0LL);
    FOR(i, 1, n + 1) {
        if (edge[i].size() >= 2) continue;
        ans = ans + solve(i);
    }
    cout << ans.fs << ' ' << ans.sc / 2 << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 0 / 48