题目分析

本题要求在树形结构中用军队封锁所有从根节点到叶子节点的路径，求最小化最大移动时间。

解题思路

问题抽象

• 给定一棵以 $1$ 为根的树，$m$ 支军队初始分布在非根节点
• 每支军队可以移动到任意非根节点建立检查点
• 移动时间为路径长度，军队可以同时移动
• 目标：让所有从根到叶子的路径上至少有一个检查点
• 要求：最小化最大移动时间

核心算法：二分答案 + 贪心调度

二分答案框架：

• 二分可能的最少时间 $T$
• 检查是否能在时间 $T$ 内完成封锁

检查函数设计：

1. 军队向上移动：每支军队在时间 $T$ 内尽量向上移动
2. 标记覆盖节点：记录哪些子树已经被完全封锁
3. 跨子树调度：用能到达根节点的军队去支援其他子树

代码解析

数据结构定义

const int N = 3e5 + 5, inf = 0x3f3f3f3f3f3f3f3f;
vector<pi>g[N];  // 邻接表存储树
int n, m, c[N];  // c[i]表示城市i的军队数量
int anc[N][16], s[N][16];  // 倍增数组：祖先和路径长度
int mn[N], d[N], a[N], b[N];  // 辅助数组
bool f[N], v[N];  // 标记数组

预处理：倍增数组

void dfs1(int u, int fa) {
    for (auto[v, w] : g[u])
        if (v != fa) {
            anc[v][0] = u, s[v][0] = w;
            for (int i = 1; i <= 15; i++) {
                anc[v][i] = anc[anc[v][i - 1]][i - 1];
                s[v][i] = s[v][i - 1] + s[anc[v][i - 1]][i - 1];
            }
            dfs1(v, u);
        }
}

建立倍增数组，用于快速计算军队向上移动的路径。

标记完全封锁的子树

void dfs2(int u, int fa) {
    if (f[u] || (g[u].size() == 1 && u != 1))
        return;
    f[u] = 1;
    for (auto[v, w] : g[u])
        if (v != fa) {
            dfs2(v, u);
            f[u] &= f[v];
        }
}

如果一个节点的所有子节点都被封锁，则该节点对应的子树被完全封锁。

检查函数

bool chk(int x) {
    memset(f, 0, sizeof(f));
    memset(v, 0, sizeof(v));
    memset(mn, 0, sizeof(mn));
    v[0] = 1;
    int c1 = 0, c2 = 0;

    // 军队向上移动
    for (int i = 1; i <= n; i++)
        if (c[i]) {
            int t = x, u = i;
            // 倍增向上跳转
            for (int j = 15; ~j; j--)
                if (anc[u][j] > 1 && s[u][j] <= t)
                    t -= s[u][j], u = anc[u][j];
            
            if (s[u][0] <= t) {
                // 能到达根节点附近
                t -= s[u][0];
                for (int j = 1; j <= c[i]; j++)
                    d[++c1] = t, b[c1] = c1;
                if (t < d[mn[u]]) mn[u] = c1;
            } else {
                // 不能到达根节点，直接封锁当前位置
                f[u] = 1;
            }
        }

    // 标记完全封锁的子树
    dfs2(1, 0);

    // 收集未被封锁的根的直接子节点
    for (auto[v, w] : g[1])
        if (!f[v]) a[++c2] = v;

    // 排序：剩余时间多的军队优先，路径长的子树优先
    sort(b + 1, b + c1 + 1, [](int x, int y) {
        return d[x] > d[y];
    });
    sort(a + 1, a + c2 + 1, [](int x, int y) {
        return s[x][0] > s[y][0];
    });

    // 贪心匹配：用军队覆盖未被封锁的子树
    int p = 1;
    for (int i = 1; i <= c2; i++) {
        if (!v[mn[a[i]]]) {
            v[mn[a[i]]] = 1;
        } else {
            while (p <= c1 && v[b[p]]) p++;
            if (p > c1 || d[b[p]] < s[a[i]][0]) return 0;
            v[b[p]] = 1;
        }
    }
    return 1;
}

主函数

signed main() {
    // 输入和初始化
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
    
    cin >> m;
    // 军队数量不足直接输出-1
    if (m < g[1].size()) {
        cout << -1;
        return 0;
    }
    
    for (int i = 1; i <= m; i++) {
        int u;
        cin >> u;
        c[u]++;
    }
    
    // 预处理和二分答案
    dfs1(1, 0);
    d[0] = inf;
    int l = 0, r = 3e14;
    while (l < r) {
        int mid = (l + r) / 2;
        if (chk(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l;
}

算法流程

1. 输入处理：读入树结构和军队分布
2. 可行性检查：如果军队数量少于根节点的度数，直接输出 $-1$
3. 预处理：建立倍增数组，支持快速向上跳转
4. 二分答案：在 $[0, 3 \times 10^{14}]$ 范围内二分最小时间
5. 检查函数：
   • 军队向上移动到极限位置
   • 标记已封锁的子树
   • 贪心匹配剩余军队和未被封锁的子树
6. 输出结果：找到的最小可行时间

复杂度分析

• 时间复杂度：$O(n \log n + n \log W)$
  • 预处理：$O(n \log n)$
  • 二分答案：$O(\log W)$ 次，每次检查 $O(n \log n)$
• 空间复杂度：$O(n \log n)$

关键技巧

1. 倍增优化：快速计算军队向上移动的极限位置
2. 贪心匹配：剩余时间多的军队匹配路径长的子树
3. 子树封锁标记：避免重复处理已封锁的路径
4. 同时移动：利用二分答案处理军队的并发移动

该算法能够高效处理 $n \leq 300,000$ 的大规模数据，是本题的经典解法。