洛谷 P1395 会议

// P1395 会议 —— 正解：换根 DP。**连 LCA 都不用，两趟遍历就完**
//
// ★★★ 这道题挂在[第 51 章](/ch/51-lca/)的题单里，理由题单注解自己写着：
//   「不是每道树上题都要上倍增」。
//
// ★ 它问的是「某个点到**所有**点的距离和」，而那个量在**父子之间只差一句话**：
//
//       f[v] = f[u] + n − 2·size[v]          （u 是 v 的父亲）
//
//   —— 会议地点从 u 挪到 v：v 那棵子树里的 size[v] 个人各近了 1 步，
//      剩下的 n − size[v] 个人各远了 1 步 ⇒ 净变化 (n − size[v]) − size[v]。
//
// ⇒ 一趟 BFS 求出 size[] 和 f[1]，再顺着 BFS 序把 f 推下去，**O(n)**。
//
// ⚠ 两处要自己乘一遍：
//   ① **距离和最大多少**：n = 5×10⁴ 的链，站在一端是 1+2+…+(n−1) = 1 249 975 000
//      —— int **恰好装得下**（余量 1.72 倍）。这里照样写 long long，代价是零。
//   ② **平局怎么办**：题面写着「选择节点编号最小的那个点」⇒ 扫的时候只能用**严格小于**。

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

const int MAXN = 50005;
int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
int fa[MAXN], sz[MAXN], order_[MAXN], n;
long long f[MAXN];

inline void addEdge(int u, int v) { to_[++ecnt] = v; nxt_[ecnt] = head_[u]; head_[u] = ecnt; }

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        if (scanf("%d %d", &u, &v) != 2) return 0;
        addEdge(u, v);
        addEdge(v, u);                        // ⚠ 无向边，两边都要存
    }

    /* ① BFS 一趟：拿到 BFS 序、父亲、深度和（⚠ 别用递归，链有 5 万层）*/
    {
        vector<char> vis(n + 1, 0);
        int cnt = 0;
        order_[cnt++] = 1; vis[1] = 1; fa[1] = 0;
        long long depSum = 0;
        vector<int> dep(n + 1, 0);
        for (int i = 0; i < cnt; i++) {
            int u = order_[i];
            depSum += dep[u];
            for (int e = head_[u]; e; e = nxt_[e]) {
                int v = to_[e];
                if (vis[v]) continue;
                vis[v] = 1; fa[v] = u; dep[v] = dep[u] + 1;
                order_[cnt++] = v;
            }
        }
        f[1] = depSum;                        // 站在 1 号点的距离和
    }

    /* ② 逆着 BFS 序求子树大小 */
    for (int i = 1; i <= n; i++) sz[i] = 1;
    for (int i = n - 1; i >= 1; i--) sz[fa[order_[i]]] += sz[order_[i]];

    /* ③ 顺着 BFS 序把 f 推下去 —— 一句话的事 */
    for (int i = 1; i < n; i++) {
        int v = order_[i];
        f[v] = f[fa[v]] + n - 2LL * sz[v];
    }

    int best = 1;
    for (int i = 2; i <= n; i++)
        if (f[i] < f[best]) best = i;         // ⚠ 严格小于：平局时留住编号小的那个
    printf("%d %lld\n", best, f[best]);
    return 0;
}

// P1395 的两笔账：这棵树长什么样，以及两条路各做多少次基本动作（机器无关）
//
// 用法：./p1395Count <csv|table> < 一份输入
//
// ★ 顺手数一个关键的东西：**有几个点同时取到最小值**（= 平局的规模）——
//   那正是错法①（`<` 写成 `<=`）的触发条件。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;
static int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], ecnt;
static int fa[MAXN], sz[MAXN], order_[MAXN], dep[MAXN], n;
static long long f[MAXN];

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        if (scanf("%d %d", &u, &v) != 2) return 0;
        to_[++ecnt] = v; nxt_[ecnt] = head_[u]; head_[u] = ecnt;
        to_[++ecnt] = u; nxt_[ecnt] = head_[v]; head_[v] = ecnt;
    }
    vector<char> vis(n + 1, 0);
    int cnt = 0;
    order_[cnt++] = 1; vis[1] = 1;
    long long depSum = 0;
    for (int i = 0; i < cnt; i++) {
        int u = order_[i];
        depSum += dep[u];
        for (int e = head_[u]; e; e = nxt_[e]) {
            int v = to_[e];
            if (vis[v]) continue;
            vis[v] = 1; fa[v] = u; dep[v] = dep[u] + 1; order_[cnt++] = v;
        }
    }
    for (int i = 1; i <= n; i++) sz[i] = 1;
    for (int i = n - 1; i >= 1; i--) sz[fa[order_[i]]] += sz[order_[i]];
    f[1] = depSum;
    for (int i = 1; i < n; i++) { int v = order_[i]; f[v] = f[fa[v]] + n - 2LL * sz[v]; }

    int maxDep = 0, best = 1, ties = 0;
    for (int i = 1; i <= n; i++) maxDep = max(maxDep, dep[i]);
    for (int i = 2; i <= n; i++) if (f[i] < f[best]) best = i;
    for (int i = 1; i <= n; i++) if (f[i] == f[best]) ties++;

    long long worst = 0;                       // 站在最差的那个点上是多少（顺手看一眼 int 够不够）
    for (int i = 1; i <= n; i++) worst = max(worst, f[i]);

    /* 两条路的基本动作：暴力每个点扫一遍所有边；正解只走两趟 */
    long long bruteEdges = (long long)n * (2LL * (n - 1));
    long long fastSteps = 2LL * n;

    vector<pair<string, string> > out;
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("best", to_string(best)));
    out.push_back(make_pair("ans", to_string(f[best])));
    out.push_back(make_pair("worst", to_string(worst)));
    out.push_back(make_pair("ties", to_string(ties)));
    out.push_back(make_pair("brute_edges", to_string(bruteEdges)));
    out.push_back(make_pair("fast_steps", to_string(fastSteps)));
    out.push_back(make_pair("ratio", to_string(bruteEdges / fastSteps)));
    if (mode == "csv") for (size_t i = 0; i < out.size(); i++) printf("%s,%s\n", out[i].first.c_str(), out[i].second.c_str());
    else for (size_t i = 0; i < out.size(); i++) printf("  %-12s %s\n", out[i].first.c_str(), out[i].second.c_str());
    return 0;
}