PA 2019 Runda 5 Podatki drogowe 题解

题目分析

这道题要求在一棵树中找到所有点对距离的第 $k$ 小值。特殊之处在于边权是 $n^{p_i}$ 的形式，这给距离的比较和计算带来了挑战。

关键难点：

• 边权是指数形式 $n^{p_i}$，直接存储会很大
• 需要高效找到第 $k$ 小的路径距离
• $n$ 可达 $5\times 10^4$，不能枚举所有点对

解题思路

核心观察

1. 距离表示：路径距离可以看作 $n$ 进制数，每位表示该边权出现的次数
2. 比较方法：从高位到低位比较，类似字符串比较
3. 分治策略：使用点分治分解问题

算法框架

代码采用了点分治 + 可持久化线段树 + 二分答案的方法：

主要步骤：

1. 重构树：将度数大于2的点拆开，使树变为二叉树
2. 点分治：递归分解树，得到路径集合
3. 哈希比较：用可持久化线段树存储路径的"指纹"
4. 二分答案：通过统计比某值小的路径数来找到第k小

代码详解

1. 数据结构定义

typedef unsigned long long LL;
const int N = 50005, M = N << 5, P = 1e9 + 7;

struct Node {
    int l, r;    // 左右儿子
    LL c, s;     // 计数和哈希和
} t[N << 9];     // 可持久化线段树
int pid;         // 节点计数器

2. 路径哈希

LL p[N];  // 基数幂 p[i] = 13331^i

void Insert(int &u, int v, int x, int a = 1, int b = n) {
    u = ++pid;
    t[u] = t[v];
    t[u].c++;           // 计数+1
    t[u].s += p[x];     // 哈希和增加
    
    if (a != b) {
        if (x <= mid)
            Insert(t[u].l, t[v].l, x, a, mid);
        else
            Insert(t[u].r, t[v].r, x, mid + 1, b);
    }
}

这里用可持久化线段树存储路径的"指纹"，每个位置记录该边权出现的次数。

3. 路径比较

bool Compare(int u, int v, int a, int b) {
    if (a == b)
        return t[u].c < t[v].c;  // 叶子节点比较计数
        
    // 从高位(右子树)开始比较
    if (t[t[u].r].s == t[t[v].r].s)
        return Compare(t[u].l, t[v].l, a, mid);
    else
        return Compare(t[u].r, t[v].r, mid + 1, b);
}

比较策略：从高次项开始比较，类似大整数比较。

4. 点分治处理

void Work(int u) {
    if (siz[u] == 1) return;
    
    // 找重心
    int x = 0, y = 0;
    FindRoot(u, 0, x, y, tot);
    
    // 分别处理两个子树
    cnt++;
    DFS(x, y, w0, 0, rl[cnt]);  // 左子树路径
    DFS(y, x, 0, 0, rr[cnt]);   // 右子树路径
    
    // 排序路径
    stable_sort(rl[cnt].begin(), rl[cnt].end(), cmp);
    stable_sort(rr[cnt].begin(), rr[cnt].end(), cmp);
    
    // 记录路径对
    for (int i = 0; i < (int)rl[cnt].size(); i++) {
        k++;
        p0[k] = cnt;  // 分治块编号
        p1[k] = i;    // 左路径索引
        pl[k] = 0;    // 右路径范围左端点
        pr[k] = (int)rr[cnt].size() - 1;  // 右端点
    }
}

5. 二分答案框架

int u = 0, v = 0;
while (!Divide(u, v)) ;  // 不断二分直到找到第k小

// 计算最终答案
Get(u, cc);  // 提取路径信息
Get(v, cc);
LL ans = 0;
for (int i = n; i >= 0; i--)
    ans = (ans * n + cc[i]) % P;  // 重建距离值

算法原理

路径表示

路径距离 $d = \sum c_i \cdot n^{p_i}$ 可以看作：

• 系数向量 $(c_1, c_2, \dots, c_n)$
• 哈希值 $\sum c_i \cdot base^{p_i}$

第k小查找

使用类似"中位数之中位数"的方法：

1. 随机选择一个候选距离
2. 统计比它小的路径数量
3. 根据比较结果调整搜索范围

复杂度分析

• 时间复杂度：$O(n \log^3 n)$
  • 点分治：$O(n \log n)$
  • 路径排序：$O(n \log^2 n)$
  • 二分查找：$O(\log n)$
• 空间复杂度：$O(n \log n)$

样例解析

对于样例：

5 8
1 2 1    # 边权 n^1 = 5
3 1 3    # 边权 n^3 = 125  
3 4 1    # 边权 5
5 3 2    # 边权 n^2 = 25

路径 $2 \to 4$：经过边 $(2,1):5$, $(1,3):125$, $(3,4):5$ 距离 = $5 + 125 + 5 = 135$

关键技巧

1. 哈希比较：用多项式哈希代替大整数比较
2. 可持久化：高效存储和比较路径信息
3. 点分治：分解路径统计问题
4. 随机抽样：在二分中高效选择pivot

总结

这道题综合运用了：

• 图论：点分治分解树结构
• 数据结构：可持久化线段树存储路径信息
• 算法：二分查找第k小元素
• 哈希技术：高效比较路径距离

通过巧妙的哈希表示和分治策略，算法在 $O(n \log^3 n)$ 时间内解决了大规模树的第k小路径问题，展示了处理复杂数值比较问题的高级技巧。