G. 最短生成樹 (sptree)

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

using pii = pair<int, int>;
template <typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define ALL(x) begin(x), end(x)
#define SZ(x) ((int)(x).size())

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

const int maxn = 30000 + 5;

vector<tuple<int, int, int>> G[maxn];
vector<pii> adj[maxn];
vector<int> sz(maxn, 1), heavy(maxn, -1);
deque<pii> dp;
int P;

pii ans{0, 0};

void dfs_heavy(int now) {
    int mx_sz = 0;
    for (auto [x, cost] : adj[now]) {
        dfs_heavy(x), sz[now] += sz[x];
        if (chmax(mx_sz, sz[x])) heavy[now] = x;
    }
    sort(ALL(adj[now]), [&](const pii &a, const pii &b) {return sz[a.first] > sz[b.first];});
}

void dfs_calc(int now, int dep, int sum) {
    if (SZ(dp) > P-dep-1 and dep <= P-1) {
        if (chmax(ans.first, dp[P-dep-1].first + sum)) ans.second = 0;
        if (ans.first == dp[P-dep-1].first + sum) ans.second += dp[P-dep-1].second;
    }
    for (auto [x, cost] : adj[now]) dfs_calc(x, dep+1, sum+cost);
}

void dfs_add(int now, int dep, int sum) {
    if (SZ(dp) <= dep) dp.eb(0, 1);
    if (chmax(dp[dep].first, sum)) dp[dep].second = 0;
    if (dp[dep].first == sum) ++dp[dep].second;
    for (auto [x, cost] : adj[now]) dfs_add(x, dep+1, sum+cost);
}

void dfs(int now, bool keep) {
    for (auto [x, cost] : adj[now]) if (x != heavy[now]) dfs(x, 0);
    if (~heavy[now]) {
        dfs(heavy[now], 1);
        for (auto &[val, cnt] : dp) val += adj[now][0].second;
    }
    dp.ef(0, 1);
    if (SZ(dp) > P-1) {
        if (chmax(ans.first, dp[P-1].first)) ans.second = 0;
        if (ans.first == dp[P-1].first) ans.second += dp[P-1].second;
    }
    for (auto [x, cost] : adj[now]) if (x != heavy[now]) dfs_calc(x, 1, cost), dfs_add(x, 1, cost);
    if (!keep) dp.clear();
}

vector<int> vis;

void dfs_sptree(int now) {
    vis[now] = 1;
    for (auto [x, cost, flag] : G[now]) {
        if (vis[x]) flag = 0;
        else if (flag) adj[now].eb(x, cost), dfs_sptree(x);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N, M; cin >> N >> M >> P;

    for (int i = 0, u, v, w; i < M; ++i) {
        cin >> u >> v >> w, --u, --v;
        G[u].eb(v, w, 0), G[v].eb(u, w, 0);
    }
    for (int i = 0; i < N; ++i) sort(ALL(G[i]));

    /// sp-dag ///

    vector<int> dis(N, INT_MAX >> 1);
    prior<pii> pq;
    pq.ee(dis[0] = 0, 0);

    while (SZ(pq)) {
        auto [_d, now] = pq.top(); pq.pop();
        if (dis[now] != _d) continue;
        for (auto [x, cost, flag] : G[now]) if (chmin(dis[x], dis[now] + cost)) pq.ee(dis[x], x);
    }

    for (int i = 0; i < N; ++i) {
        for (auto &[x, cost, flag] : G[i]) flag = (dis[x] == dis[i] + cost);
    }

    vis.assign(N, 0);
    dfs_sptree(0);

    /// dsu on tree ///

    dfs_heavy(0);
    dfs(0, 1);

    cout << ans.first << " " << ans.second << "\n";

    return 0;
}