HDU 5016 Mart Master II：樹上點分治求最大占領點數

題目大意

給定一棵樹，部分節點為基站。每個節點最近的基站距離與編號預處理已知。現需在樹上選一個點作為「主基站」，使其能「占領」最多節點。占領條件：對於節點 x，若 dis(x, center) + dis(x, nearest_base[x]) < d[nearest_base[x]]，則被占領。求最大占領數。

解題思路：點分治

1. 預處理：兩遍 DFS 求每個點到最近基站的距離 d[u] 及基站編號 id[u]。
2. 點分治框架：
   • 求子樹大小 getsize、找重心 getroot。
   • 從重心出發 DFS 計算各點到重心距離 dis[u]，並記錄 F[tot] = {d[u] - dis[u], id[u]}。
   • 對 F 按 (val, id) 排序。
   • 對當前子樹每個點 u，二分查找滿足 F[k].val < dis[u] 或 (val == dis[u] && id ≤ id[u]) 的最大索引，即為不被占領的數量。子樹大小減去該值即為占領數。
   • 遞歸處理各子樹，全局維護最大值。

關鍵代碼結構

// 預處理最近基站
void dfs1(int u, int fa) { ... }
void dfs2(int u, int fa) { ... }

// 點分治核心
void getsize(int u, int fa) { ... }
void getroot(int u, int fa, int s) { ... }
void getdis(int u, int fa, int l) {
    dis[u] = l;
    F[tot].dis = d[u] - l;
    F[tot++].id = id[u];
    for (int i = head[u]; i != -1; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa || vis[v]) continue;
        getdis(v, u, l + edge[i].w);
    }
}
int BS(int l, int u) { // 二分查找
    int low = 0, high = tot - 1, mid, ans = -1;
    while (low <= high) {
        mid = (low + high) >> 1;
        if (F[mid].dis < l || (F[mid].dis == l && F[mid].id <= u)) {
            ans = mid; low = mid + 1;
        } else high = mid - 1;
    }
    return ans;
}
void solve(int u) {
    // ... 標準分治流程
}

複雜度分析

點分治層數 O(log n)，每層處理所有節點，排序與二分 O(n log n)，總體 O(n log² n)。n ≤ 1e5 可通過。