数据中心通信问题题解

问题分析

我们有一棵树，需要选择一个点集 S 满足：

1. u ∈ S（u 是询问点）
2. ∀x,y ∈ S, dist(x,y) ≤ d
3. 最大化总延迟：∑{x∈S}∑{y∈S} dist(x,y)

---

关键观察

设选出的点集为 S，对于固定 u：

1. 直径限制：因为任意两点距离 ≤ d，所以 S 的直径（最远两点距离）≤ d

2. 中心化思想：对于直径 ≤ d 的集合，可以找到其"中心"：

   • 如果直径 d 是偶数，中心是一个点
   • 如果直径 d 是奇数，中心是一条边

   本题中 d 是固定整数

3. 重定义问题：对于询问 u，我们要找包含 u 且直径 ≤ d 的连通子图，最大化其中所有点对距离之和

4. 公式转化：总延迟 = ∑{x∈S}∑{y∈S} dist(x,y) = 2∑_{x∈S} dep(x) × cnt - 其他项？
   其中 dep(x) 是到某个根的距离，cnt 是 S 大小

更好的公式：设根为 r，则 dist(x,y) = dep(x) + dep(y) - 2×dep(LCA(x,y))

所以总延迟 = ∑{x∈S}∑{y∈S} [dep(x) + dep(y) - 2×dep(LCA(x,y))]
= 2|S|∑{x∈S} dep(x) - 2∑{x∈S}∑_{y∈S} dep(LCA(x,y))

---

简化与转化

观察：最大化总延迟等价于最大化"离心率和"：∑{x∈S} eccentricity(x)，其中 eccentricity(x) = max{y∈S} dist(x,y)

引理：在直径 ≤ d 的集合 S 中，总延迟最大时，S 应包含以 u 为中心、半径为 d/2 的"球"中的所有点

证明思路：

• 加入新点增加的总延迟 = 该点到 S 中所有点距离之和
• 距离 ≤ d 时，离 u 越近的点，到 S 中点的平均距离越小
• 所以优先选择离 u 远的点

---

算法思路

对于每个询问 u，我们考虑以 u 为中心的"影响范围"：

情况1：d 为偶数

设 R = d/2，则最优 S 是：所有距离 u ≤ R 的点

因为：

1. 这些点互相距离 ≤ d（三角不等式）
2. 加入更远的点会违反直径约束

此时总延迟计算： 设 S 的大小为 m，点按到 u 的距离分组 总延迟 = ∑{x∈S}∑{y∈S} dist(x,y)
可以 O(m) 计算，但 m 可能很大

优化计算： dist(x,y) = dist(x,u) + dist(y,u) - 2×dist(LCA(x,y), u)
但 LCA 计算复杂，需要更快方法

更好方法：以 u 为根建立树，设 dep[v] = dist(u,v)

则 dist(x,y) = dep[x] + dep[y] - 2×dep[LCA(x,y)]
总延迟 = ∑{x∈S}∑{y∈S} (dep[x] + dep[y] - 2×dep[LCA(x,y)])
= 2m∑{x∈S} dep[x] - 2∑{x∈S}∑_{y∈S} dep[LCA(x,y)]

难点在第二项，但注意到 S 是连通块（子树的一部分），可以用 DP 计算

情况2：d 为奇数

此时最优 S 的中心是一条边 (u,v)，包含 u 且直径 = d

需要枚举 u 的邻边作为"中心边"，计算最大总延迟

---

具体算法步骤

预处理

1. 计算任意两点距离：因为 n ≤ 5e5，不能 O(n²)，需要其他方法
2. 预处理 LCA：O(n log n)，支持 O(1) 查询两点距离

对于每个询问 u

步骤1：找到距离 u ≤ R 的所有点（R = ⌊d/2⌋）

• 以 u 为根 BFS/DFS，记录距离
• 收集所有距离 ≤ R 的点

步骤2：计算这些点组成集合的总延迟 方法 A（暴力 O(k²)，k 为点数）：

total = 0
for x in S:
    for y in S:
        total += dist(x,y)
return total

但 k 可能很大（接近 n），需要优化

方法 B（树形 DP 优化）： 以 u 为根，设 f[v] = ∑_{x∈S_v} dist(u,x) 的某种和 需要设计状态转移

实际简化：对于直径 ≤ d 的连通块，我们可以证明最优解是某个节点的子树中深度不超过 R 的部分

证明：如果 S 不连通，添加连接部分不会减少总延迟（因为增加了点对距离） 所以 S 是连通的，且包含 u，所以是以 u 为根的子树的一部分

因此算法： 对于每个 u，考虑以 u 为根的树，选择深度 ≤ R 的子树，最大化总延迟

但这样可能不是最优（因为最优可能包含 u 的祖先）

所以需要换根 DP

---

最终算法框架

预处理：

1. 计算以 1 为根的深度 depth[1][v]
2. 预处理 LCA（倍增或树剖）

对于每个询问 u：

1. 以 u 为根重新计算深度（通过换根）
2. 找到所有 depth[u][v] ≤ R 的点（R = ⌊d/2⌋）
3. 计算这些点的总延迟

总延迟计算优化： 设 S = {v | dist(u,v) ≤ R} 总延迟 = ∑{x∈S}∑{y∈S} dist(x,y)

= ∑{x∈S}∑{y∈S} [dist(u,x) + dist(u,y) - 2×dist(u, LCA(x,y))]
= 2|S|∑{x∈S} dist(u,x) - 2∑{x∈S}∑_{y∈S} dist(u, LCA(x,y))

设 T = ∑{x∈S}∑{y∈S} dist(u, LCA(x,y))

对于固定 u，我们可以用树形 DP 计算 T： 定义 g[v] = 以 v 为根的子树中，属于 S 的点数 则 dist(u, LCA(x,y)) 可以分解

关键技巧：对于每个点 w，考虑它作为 LCA 的次数 如果 w 的子树中有 cnt[w] 个点在 S 中，那么以 w 为 LCA 的点对数为 C(cnt[w], 2) - ∑_{child c} C(cnt[c], 2) 每个这样的点对贡献 dist(u,w)

所以 T = ∑{w} dist(u,w) × [C(cnt[w], 2) - ∑{child c} C(cnt[c], 2)]

---

完整算法

1. 预处理：

   • 建立 LCA 结构（O(n log n)）
   • 计算任意点作为根时，各点的 cnt 值

2. 对于每个询问 u：

   • 以 u 为根，计算 depth[u][v]（实际不需要显式计算所有，只需 BFS）
   • 收集所有 depth ≤ R 的点，标记为 S
   • 计算每个点 w 的 cnt[w] = w 子树中属于 S 的点数
   • 计算 T = ∑{w} depth[w] × [C(cnt[w], 2) - ∑{child c} C(cnt[c], 2)]
   • 计算 sum_dist = ∑_{x∈S} depth[x]
   • 答案 = 2|S| × sum_dist - 2T

3. 复杂度：

   • 预处理 O(n log n)
   • 每个询问 O(n) BFS + O(n) DP
   • 总 O(qn)，但 q ≤ 10，n ≤ 5e5，可以接受（5e6 操作）

---

代码框架

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

const int MAXN = 500005;
const int LOG = 20;

int n, d, q;
vector<int> G[MAXN];

// LCA 预处理
int depth[MAXN], up[MAXN][LOG];

void dfs_lca(int u, int p) {
    depth[u] = depth[p] + 1;
    up[u][0] = p;
    for (int i = 1; i < LOG; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }
    for (int v : G[u]) {
        if (v != p) dfs_lca(v, u);
    }
}

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

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

// 主求解函数
long long solve_for_u(int u) {
    int R = d / 2;  // 向下取整
    
    // BFS 收集距离 ≤ R 的点
    vector<int> nodes;
    vector<int> dist_from_u(n+1, -1);
    queue<int> qq;
    
    dist_from_u[u] = 0;
    qq.push(u);
    nodes.push_back(u);
    
    while (!qq.empty()) {
        int v = qq.front(); qq.pop();
        if (dist_from_u[v] == R) continue;
        
        for (int w : G[v]) {
            if (dist_from_u[w] == -1) {
                dist_from_u[w] = dist_from_u[v] + 1;
                qq.push(w);
                nodes.push_back(w);
            }
        }
    }
    
    // 建立以 u 为根的树结构
    vector<vector<int>> tree(n+1);
    vector<bool> visited(n+1, false);
    
    function<void(int)> build_tree = [&](int v) {
        visited[v] = true;
        for (int w : G[v]) {
            if (!visited[w] && dist_from_u[w] != -1) {
                tree[v].push_back(w);
                build_tree(w);
            }
        }
    };
    
    build_tree(u);
    
    // 计算 cnt[v]：子树中属于 S 的点数
    vector<int> cnt(n+1, 0);
    
    function<void(int)> compute_cnt = [&](int v) {
        cnt[v] = 1;  // v 自身在 S 中
        for (int w : tree[v]) {
            compute_cnt(w);
            cnt[v] += cnt[w];
        }
    };
    
    compute_cnt(u);
    
    // 计算答案
    long long m = nodes.size();  // |S|
    long long sum_dist = 0;
    for (int v : nodes) {
        sum_dist += dist_from_u[v];
    }
    
    long long T = 0;
    function<void(int)> compute_T = [&](int v) {
        long long pairs_here = 1LL * cnt[v] * (cnt[v] - 1) / 2;
        long long pairs_child = 0;
        
        for (int w : tree[v]) {
            pairs_child += 1LL * cnt[w] * (cnt[w] - 1) / 2;
            compute_T(w);
        }
        
        T += dist_from_u[v] * (pairs_here - pairs_child);
    };
    
    compute_T(u);
    
    long long ans = 2 * m * sum_dist - 2 * T;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> d;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    // 以 1 为根建立 LCA
    depth[0] = -1;
    dfs_lca(1, 0);
    
    cin >> q;
    while (q--) {
        int u;
        cin >> u;
        cout << solve_for_u(u) << "\n";
    }
    
    return 0;
}

---

算法复杂度分析

1. 预处理：O(n log n) 建立 LCA
2. 每个询问：
   • BFS 收集节点：O(n)
   • 建立树结构：O(n)
   • 计算 cnt 和 T：O(n)
   • 总计：O(n) 每个询问

总复杂度：O(n log n + qn)，对于 n ≤ 5e5，q ≤ 10，可以接受（约 5e6 操作）

---

优化与注意事项

1. 内存优化：实际不需要存储多棵树的完整结构，可以复用数组
2. 边界情况：d = 0 时，S = {u}，答案为 0
3. d 为奇数：需要稍微调整 R 的计算，考虑中心边的情况

---

总结

本题的核心是：

1. 将问题转化为寻找以 u 为中心、半径为 ⌊d/2⌋ 的连通块
2. 用树形 DP 高效计算点对距离之和
3. 利用 LCA 分解距离公式，避免 O(k²) 的计算

该解法充分利用了树结构的性质，在 q 较小的情况下能够高效求解。