洛谷 P3478 STA-Station

// ✗ P3478 第一版：每个点都当一次根，各跑一次 BFS 把深度加起来
//
// ★★★ 它的**答案永远是对的** —— 它错在跑不完：O(n²)，而题面 n ≤ 10⁶。
//    ⇒ 官方样例挡不住它，对拍也挡不住它（两版答案逐组相同）。
//      这类错法只有一种发现办法：**数次数 ＋ 算规模**（见 [P5019] 那一页）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }

    ll best = -1;
    int who = 1;
    vector<int> dep(n + 1), st;
    vector<char> vis(n + 1);
    for (int r = 1; r <= n; r++) {
        fill(vis.begin(), vis.end(), 0);
        st.clear();
        st.push_back(r);
        vis[r] = 1;
        dep[r] = 0;
        ll sum = 0;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            sum += dep[u];
            for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; dep[v] = dep[u] + 1; st.push_back(v); }
        }
        if (sum > best) { best = sum; who = r; }
    }
    cout << who << '\n';
    return 0;
}

// P3478 STA-Station —— 正解：换根 DP，两遍 O(n)
//
// 第一遍（以 1 为根）：算出每棵子树的大小 size[u]，以及「以 1 为根时所有点的深度和」f[1]。
// 第二遍：把根从 u 挪到它的儿子 v，谁的深度变了？
//
//     · v 的子树里那 size[v] 个点，各**少**走一条边  ⇒ 减 size[v]
//     · 其余 n - size[v] 个点，各**多**走一条边      ⇒ 加 n - size[v]
//
//     ⇒ f[v] = f[u] + n - 2 × size[v]        ← 一次 O(1) 就推到了下一个点
//
// ⚠ 两件在这道题上会真的挂人的事：
//   ① **必须 long long**：n = 10⁶ 排成一条链时深度和约 5 × 10¹¹，int 装不下；
//   ② **不能用递归**：10⁶ 层 DFS 直接爆栈（同题单的 [P1122] n ≤ 16000 就没事 —— 见那一页）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;

    vector<int> head(n + 1, -1), nxt(2 * (n > 1 ? n - 1 : 1)), to(2 * (n > 1 ? n - 1 : 1));
    int cnt = 0;
    auto addEdge = [&](int u, int v) { to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt++; };
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        addEdge(u, v);
        addEdge(v, u);
    }

    // ① 迭代式 DFS：求出 BFS/DFS 序、父亲、子树大小、深度和
    vector<int> par(n + 1, 0), ord;
    vector<ll> sz(n + 1, 1), f(n + 1, 0);
    ord.reserve(n);
    {
        vector<int> st{1};
        vector<char> vis(n + 1, 0);
        vis[1] = 1;
        vector<int> dep(n + 1, 0);
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            ord.push_back(u);
            for (int e = head[u]; e != -1; e = nxt[e]) {
                int v = to[e];
                if (vis[v]) continue;
                vis[v] = 1;
                par[v] = u;
                dep[v] = dep[u] + 1;
                st.push_back(v);
            }
        }
        for (int u : ord) f[1] += dep[u];
        for (int i = (int)ord.size() - 1; i >= 1; i--) sz[par[ord[i]]] += sz[ord[i]];
    }

    // ② 换根：按 DFS 序从上往下推
    for (size_t i = 1; i < ord.size(); i++) {
        int v = ord[i];
        f[v] = f[par[v]] + n - 2 * sz[v];
    }

    int best = 1;
    for (int u = 2; u <= n; u++) if (f[u] > f[best]) best = u;
    cout << best << '\n';
    return 0;
}

// ✗ P3478：换根公式少减了一次
//
//     写成  f[v] = f[u] + n - size[v]        （正确的是 n - 2 × size[v]）
//
// ★ 它算了什么：它只记得「子树外面那 n - size[v] 个点各多走一步」，
//    忘了「子树里面那 size[v] 个点各少走一步」——**只算了涨的那一半，没算落的那一半**。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); }

    vector<int> par(n + 1, 0), ord, dep(n + 1, 0);
    vector<ll> sz(n + 1, 1), f(n + 1, 0);
    ord.reserve(n);
    vector<int> st{1};
    vector<char> vis(n + 1, 0);
    vis[1] = 1;
    while (!st.empty()) {
        int u = st.back(); st.pop_back();
        ord.push_back(u);
        for (int v : adj[u]) if (!vis[v]) { vis[v] = 1; par[v] = u; dep[v] = dep[u] + 1; st.push_back(v); }
    }
    for (int u : ord) f[1] += dep[u];
    for (int i = (int)ord.size() - 1; i >= 1; i--) sz[par[ord[i]]] += sz[ord[i]];
    for (size_t i = 1; i < ord.size(); i++) { int v = ord[i]; f[v] = f[par[v]] + n - sz[v]; }   // ← 这里

    int best = 1;
    for (int u = 2; u <= n; u++) if (f[u] > f[best]) best = u;
    cout << best << '\n';
    return 0;
}