洛谷 P2680 [NOIP 2015 提高组] 运输计划

// P2680 [NOIP 2015 提高组] 运输计划 —— 正解：**二分答案 ＋ 边差分 ＋ LCA**，三件东西合在一起
//
// ★★★ 这道题是本书第 9 / 51 / 52 三章的合体，而**难点全在「二分之后那半句 check」上**。
//
// 二分那一半好想：答案（最长的那个计划要花多久）具有单调性 ——
//   如果 T 秒能做到，那 T+1 秒当然也能。⇒ 二分 T，问一句「T 秒够不够」。
//
// ★★★ 而 check(T) 那一半是整道题：设「超时的计划」= 长度 > T 的那些，一共 c 条。
//   ① 那条虫洞**必须被这 c 条路径全都经过** —— 只挖一条边，谁没被挖到谁就还是超时。
//      ⇒ 「一条边被几条路径经过」正是**边差分**：`d[u]++, d[v]++, d[lca] -= 2`，
//        再一趟子树求和，`d[v]` 就是「v 和它父亲之间那条边被盖了几次」。
//      ⇒ 要找的是 `d[v] == c` 的边。
//   ⚠⚠ ② **光被全覆盖还不够，省下来的时间得够多**：
//      挖掉边 e 之后，最长的那条超时计划变成 `maxBad − w(e)`，这个数**也要 ≤ T**。
//      ⇒ 判据是 `d[v] == c && w(v) >= maxBad - T`。**漏掉后半句是这道题最常见的 WA。**
//
// ⇒ 复杂度：一次 LCA 预处理 O(n log n) ＋ 二分 O((n + m) log(Σt))。
// ★ 题面末尾专门写着「**请注意常数因子带来的程序效率上的影响**」——
//   所以倍增表只能建**一次**，绝不能放进二分里（见 p2680Rebuild.cpp）。
//
// ★ 「要不要 long long」是一句乘法：路径最长 (n−1)·max t = 3×10⁵ × 1000 = **3×10⁸**，
//   而 int 的上限是 2 147 483 647 ⇒ **够，余量 7.16 倍**。这一版全程用 int。

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

const int MAXN = 300005;
const int LOG = 19;

int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], wt_[MAXN * 2], ecnt;
int up[MAXN][LOG], dep[MAXN], dist_[MAXN], wpar[MAXN], order_[MAXN], d[MAXN];
int pu[MAXN], pv[MAXN], pl[MAXN], plen[MAXN];
int n, m;

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

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[u][j];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; }
    return up[u][0];
}

/* T 秒够不够？ */
bool check(int T) {
    int c = 0, maxBad = 0;
    for (int i = 0; i < m; i++) if (plen[i] > T) { c++; maxBad = max(maxBad, plen[i]); }
    if (c == 0) return true;                     // ★ 一条都没超时，连虫洞都不用挖

    memset(d, 0, sizeof(int) * (n + 1));
    for (int i = 0; i < m; i++) if (plen[i] > T) { d[pu[i]]++; d[pv[i]]++; d[pl[i]] -= 2; }
    for (int i = n - 1; i >= 1; i--) d[up[order_[i]][0]] += d[order_[i]];

    for (int i = 1; i < n; i++) {
        int v = order_[i];                       // ⚠ order_[0] 是根，跳过（根头上没有边）
        if (d[v] == c && wpar[v] >= maxBad - T) return true;
    }
    return false;
}

int main() {
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n - 1; i++) {
        int x, y, w;
        if (scanf("%d %d %d", &x, &y, &w) != 3) return 0;
        addEdge(x, y, w); addEdge(y, x, w);
    }
    {
        vector<char> vis(n + 1, 0);
        int cnt = 0;
        order_[cnt++] = 1; vis[1] = 1; dep[1] = 1; up[1][0] = 0; dist_[1] = 0;
        for (int i = 0; i < cnt; i++) {
            int u = order_[i];
            for (int e = head_[u]; e; e = nxt_[e]) {
                int v = to_[e];
                if (vis[v]) continue;
                vis[v] = 1; dep[v] = dep[u] + 1; up[v][0] = u;
                dist_[v] = dist_[u] + wt_[e]; wpar[v] = wt_[e];
                order_[cnt++] = v;
            }
        }
    }
    for (int j = 1; j < LOG; j++)
        for (int v = 1; v <= n; v++)
            up[v][j] = up[up[v][j - 1]][j - 1];

    int hi = 0;
    for (int i = 0; i < m; i++) {
        if (scanf("%d %d", &pu[i], &pv[i]) != 2) return 0;
        pl[i] = lca(pu[i], pv[i]);
        plen[i] = dist_[pu[i]] + dist_[pv[i]] - 2 * dist_[pl[i]];
        hi = max(hi, plen[i]);
    }

    int lo = 0;                                  // ⚠ 下界是 0，不是 1：t 可以全为 0
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (check(mid)) hi = mid; else lo = mid + 1;
    }
    printf("%d\n", lo);
    return 0;
}

// P2680 的账：这份数据长什么样、答案是多少、二分要问几轮（都是机器无关的数）
//
// 用法：./p2680Count <csv|table> < 一份输入
//
// ★ 顺手数三个决定成败的东西：
//   ① **超时计划里有几个的 LCA 不是根** —— 那正是错法②（边差分写成点差分）的触发条件；
//   ② **答案是不是 0** —— 那是错法③（二分下界写成 1）的触发条件；
//   ③ **最长路径有多长** —— 「要不要 long long」那句乘法的左边。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int LOG = 19;
static int head_[MAXN], nxt_[MAXN * 2], to_[MAXN * 2], wt_[MAXN * 2], ecnt;
static int up[MAXN][LOG], dep[MAXN], wpar[MAXN], order_[MAXN], d[MAXN];
static long long dist_[MAXN];
static int pu[MAXN], pv[MAXN], pl[MAXN];
static long long plen[MAXN];
static int n, m;

static int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[u][j];
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; }
    return up[u][0];
}

static long long badCnt, badNotRootLca;
static bool check(long long T) {
    long long c = 0, maxBad = 0;
    badNotRootLca = 0;
    for (int i = 0; i < m; i++) if (plen[i] > T) {
        c++; maxBad = max(maxBad, plen[i]);
        if (pl[i] != 1) badNotRootLca++;
    }
    badCnt = c;
    if (c == 0) return true;
    memset(d, 0, sizeof(int) * (n + 1));
    for (int i = 0; i < m; i++) if (plen[i] > T) { d[pu[i]]++; d[pv[i]]++; d[pl[i]] -= 2; }
    for (int i = n - 1; i >= 1; i--) d[up[order_[i]][0]] += d[order_[i]];
    for (int i = 1; i < n; i++) {
        int v = order_[i];
        if (d[v] == c && wpar[v] >= maxBad - T) return true;
    }
    return false;
}

int main(int argc, char** argv) {
    string mode = argc > 1 ? argv[1] : "table";
    if (scanf("%d %d", &n, &m) != 2) return 0;
    for (int i = 0; i < n - 1; i++) {
        int x, y, w;
        if (scanf("%d %d %d", &x, &y, &w) != 3) return 0;
        to_[++ecnt] = y; wt_[ecnt] = w; nxt_[ecnt] = head_[x]; head_[x] = ecnt;
        to_[++ecnt] = x; wt_[ecnt] = w; nxt_[ecnt] = head_[y]; head_[y] = ecnt;
    }
    {
        vector<char> vis(n + 1, 0);
        int c = 0;
        order_[c++] = 1; vis[1] = 1; dep[1] = 1; up[1][0] = 0;
        for (int i = 0; i < c; i++) {
            int u = order_[i];
            for (int e = head_[u]; e; e = nxt_[e]) {
                int v = to_[e];
                if (vis[v]) continue;
                vis[v] = 1; dep[v] = dep[u] + 1; up[v][0] = u;
                dist_[v] = dist_[u] + wt_[e]; wpar[v] = wt_[e]; order_[c++] = v;
            }
        }
    }
    for (int j = 1; j < LOG; j++) for (int v = 1; v <= n; v++) up[v][j] = up[up[v][j - 1]][j - 1];

    int maxDep = 0;
    for (int i = 1; i <= n; i++) maxDep = max(maxDep, dep[i]);

    long long hi = 0, lcaRoot = 0;
    for (int i = 0; i < m; i++) {
        if (scanf("%d %d", &pu[i], &pv[i]) != 2) return 0;
        pl[i] = lca(pu[i], pv[i]);
        if (pl[i] == 1) lcaRoot++;
        plen[i] = dist_[pu[i]] + dist_[pv[i]] - 2 * dist_[pl[i]];
        hi = max(hi, plen[i]);
    }
    long long maxLen = hi, lo = 0, rounds = 0;
    while (lo < hi) { long long mid = lo + (hi - lo) / 2; rounds++; if (check(mid)) hi = mid; else lo = mid + 1; }
    long long ans = lo;
    check(ans);                                   // 把「答案那一轮」的两个计数重新算一遍
    long long badAtAns = badCnt, badNotRoot = badNotRootLca;

    /* 暴力那条路：n−1 条边 × m 个计划 × 路径长度 */
    long long bruteSteps = 0;
    for (int i = 0; i < m; i++) {
        long long plenNodes = (dep[pu[i]] - dep[pl[i]]) + (dep[pv[i]] - dep[pl[i]]) + 1;
        bruteSteps += plenNodes;
    }
    bruteSteps *= (long long)(n - 1);
    long long fastSteps = (long long)n * (LOG - 1) + rounds * (long long)(n + m);

    vector<pair<string, string> > out;
    out.push_back(make_pair("n", to_string(n)));
    out.push_back(make_pair("m", to_string(m)));
    out.push_back(make_pair("maxdep", to_string(maxDep)));
    out.push_back(make_pair("maxlen", to_string(maxLen)));
    out.push_back(make_pair("ans", to_string(ans)));
    out.push_back(make_pair("ans_is_zero", to_string(ans == 0 ? 1 : 0)));
    out.push_back(make_pair("lca_root", to_string(lcaRoot)));
    out.push_back(make_pair("bad_at_ans", to_string(badAtAns)));
    out.push_back(make_pair("bad_notroot_lca", to_string(badNotRoot)));
    out.push_back(make_pair("rounds", to_string(rounds)));
    out.push_back(make_pair("brute_steps", to_string(bruteSteps)));
    out.push_back(make_pair("fast_steps", to_string(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("  %-18s %s\n", out[i].first.c_str(), out[i].second.c_str());
    return 0;
}