题目理解

这是 BalticOI 2015 File Paths 问题的解决方案。题目要求判断对于每个文件，能否通过添加一个符号链接使得其路径长度恰好为 $k$。

代码思路解析

1. 数据结构建立

将文件系统建模为树结构：

addedge(p, i, l + 1);  // 目录名长度+1（因为要加"/"）

• 节点0表示根目录
• 边权为目录名长度 + 1（包含斜杠）

2. DFS预处理

void dfs(int x, int sum) {
    dist[x] = sum;  // 从根到x的路径长度
    cont[sum] = 1;  // 标记该长度存在
    // 记录DFS序区间
    lson[x] = ++tst;
    seq[tst] = x;
    rson[x] = tst;
}

• 计算每个节点到根的距离
• 记录DFS序用于子树操作

3. 主要判断逻辑

情况1：直接路径满足

int rem = k - (dist[p] + l + 1);
if (rem >= 0) {
    for (int j = 1; j <= n; j++) {
        if (rem % (dist[j] + 1 + s) == 0) {
            ans[i] = 1;  // 找到解
            break;
        }
    }
}

检查是否可以通过在某个目录添加符号链接来达到目标长度。

情况2：在祖先路径上检查

while (1) {
    int tmp = k - sum;
    if (tmp < 0) break;
    if (cont[tmp]) {  // 存在该长度的路径
        ans[i] = 1;
        break;
    }
    // 向上移动到父节点
    sum += lst[pos];
    pos = fa[pos];
}

检查在文件祖先路径上的某个点添加符号链接是否可行。

情况3：子树内检查（使用solve函数）

void solve(int x) {
    // 标记当前子树的所有路径长度
    for (int i = lson[x]; i <= rson[x]; i++) {
        f[dist[seq[i]] - dist[x] + s + 1]++;
    }
    
    // 处理当前节点的查询
    for (auto q : query[x]) {
        int val = q.second;
        // 检查val的因子是否在f中出现
        for (int j = 1; j * j <= val; j++) {
            if (val % j) continue;
            if (f[j] || f[val / j]) {
                ans[q.first] = 1;
                break;
            }
        }
    }
    
    // 递归处理子节点
    for (int i = head[x]; i != -1; i = nxt[i]) {
        int y = ver[i];
        solve(y);
    }
    
    // 回溯，移除当前子树的标记
    for (int i = lson[x]; i <= rson[x]; i++) {
        f[dist[seq[i]] - dist[x] + s + 1]--;
    }
}

关键技巧

1. 树结构建模

将文件系统转化为树，便于路径计算

2. DFS序应用

利用DFS序高效处理子树操作

3. 因子分解优化

通过检查目标值的因子来避免暴力枚举

4. 多情况覆盖

分别处理：

• 直接路径满足
• 祖先路径添加符号链接
• 子树内路径组合

复杂度分析

• DFS预处理：$O(n)$
• 情况1检查：$O(n^2)$（最坏情况）
• 情况2检查：$O(n \cdot \text{深度})$
• 情况3检查：$O(n \cdot \sqrt{k})$（因子分解）

总结

这个解法是典型的树形结构处理问题，通过：

1. 树结构建模：将文件系统转化为树
2. DFS预处理：计算路径长度和子树信息
3. 多策略检查：覆盖所有可能的符号链接位置
4. 数学优化：利用因子分解减少枚举量

体现了竞赛中树形问题和路径计算的常见处理技巧。