题解 :

问题分析

我们有 $n$ 个点位构成一棵有根树，点 1 是山顶。每个点 $i$ 有参数：$l_i, r_i, h_i$，分别表示冲刺范围的下界、上界和高度限制。

从点 $i$ 出发，可以进行两种操作：

1. 冲刺：选择 $k \in [l_i, r_i]$，跳到 $i$ 的 $k$ 级祖先
2. 休息：选择 $i$ 的一个儿子 $j$（如果存在），跳到 $j$

关键约束：如果在点 $i$ 进行冲刺，那么之后所有冲刺到达的点 $j$ 必须满足 $d_j < d_i - h_i$，其中 $d_j$ 是点 $j$ 的深度。

要求计算从每个点 $i (2 \leq i \leq n)$ 出发到达山顶的合法路径数。

算法思路：树形DP + 深度限制

设 $f[i]$ 表示从点 $i$ 出发到达山顶的合法路径数。

状态转移需要考虑：

1. 直接冲刺到山顶（如果可能）
2. 冲刺到某个祖先，然后从祖先继续
3. 休息到某个儿子，然后从儿子继续

但是，约束条件使得转移变得复杂：从点 $i$ 冲刺到祖先 $anc$ 后，从 $anc$ 继续时，后续路径中所有冲刺到达的点深度必须 $< d_i - h_i$。

重新定义状态

更精确定义：

• $f[i]$：从点 $i$ 出发的总合法路径数
• $g[i][lim]$：从点 $i$ 出发，且当前深度限制为 $lim$ 的合法路径数（$lim$ 表示后续冲刺到达的点深度必须 $< lim$）

但由于 $n$ 最大 $10^5$，不能存储二维状态。我们需要优化。

关键观察：

1. 从点 $i$ 出发时，初始限制是 $lim_i = d_i - h_i$
2. 当从点 $i$ 冲刺到祖先 $anc$ 时：
   • 如果 $d_{anc} \geq lim_i$，则不能从 $anc$ 继续（违反限制）
   • 如果 $d_{anc} < lim_i$，则从 $anc$ 继续时，限制更新为 $min(lim_i, d_{anc} - h_{anc})$

所以我们可以定义：$F[i]$ 表示从点 $i$ 出发，且初始限制为 $d_i - h_i$ 的路径数。

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 998244353
#define MAXN 100010

typedef long long ll;

int n;
int parent[MAXN], depth[MAXN];
int l[MAXN], r[MAXN], h[MAXN];
ll ans[MAXN];

// 邻接表
int head[MAXN], nxt[MAXN], to[MAXN], ecnt;

void add_edge(int u, int v) {
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}

// 倍增
int up[MAXN][20];
int LOG;

void init_binary_lifting() {
    LOG = 0;
    while ((1 << LOG) <= n) LOG++;
    
    for (int i = 1; i <= n; i++) {
        up[i][0] = parent[i];
    }
    
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }
}

int kth_ancestor(int u, int k) {
    if (k > depth[u]) return 0;
    for (int j = 0; j < LOG; j++) {
        if (k & (1 << j)) {
            u = up[u][j];
        }
    }
    return u;
}

// 树状数组
ll bit[MAXN];

void bit_init() {
    memset(bit, 0, sizeof(bit));
}

void bit_add(int idx, ll val) {
    while (idx <= n) {
        bit[idx] = (bit[idx] + val) % MOD;
        idx += idx & -idx;
    }
}

ll bit_sum(int idx) {
    ll res = 0;
    while (idx > 0) {
        res = (res + bit[idx]) % MOD;
        idx -= idx & -idx;
    }
    return res;
}

ll range_sum(int l, int r) {
    if (l > r) return 0;
    return (bit_sum(r) - bit_sum(l-1) + MOD) % MOD;
}

// 主算法
ll sum_children[MAXN];  // 所有孩子的ans之和

void dfs_prep(int u) {
    sum_children[u] = 0;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        dfs_prep(v);
        sum_children[u] = (sum_children[u] + ans[v]) % MOD;
    }
}

void solve() {
    // 计算深度
    depth[1] = 0;
    for (int i = 2; i <= n; i++) {
        depth[i] = depth[parent[i]] + 1;
    }
    
    // 初始化倍增
    init_binary_lifting();
    
    // 准备孩子和
    dfs_prep(1);
    
    // 按深度从大到小处理节点
    int max_depth = 0;
    for (int i = 1; i <= n; i++) {
        if (depth[i] > max_depth) max_depth = depth[i];
    }
    
    // 收集每个深度的节点
    int** depth_nodes = (int**)malloc((max_depth + 1) * sizeof(int*));
    int* depth_cnt = (int*)calloc(max_depth + 1, sizeof(int));
    
    for (int i = 1; i <= n; i++) {
        depth_cnt[depth[i]]++;
    }
    
    for (int d = 0; d <= max_depth; d++) {
        depth_nodes[d] = (int*)malloc(depth_cnt[d] * sizeof(int));
        depth_cnt[d] = 0;  // 重置为索引
    }
    
    for (int i = 1; i <= n; i++) {
        int d = depth[i];
        depth_nodes[d][depth_cnt[d]++] = i;
    }
    
    // 自底向上DP
    for (int d = max_depth; d >= 0; d--) {
        for (int i = 0; i < depth_cnt[d]; i++) {
            int u = depth_nodes[d][i];
            
            // 初始化为孩子和（休息操作）
            ans[u] = sum_children[u];
            
            // 冲刺操作
            // 冲刺距离范围：k in [l[u], r[u]]
            int min_k = l[u];
            int max_k = r[u];
            if (max_k > depth[u]) max_k = depth[u];
            
            int limit = depth[u] - h[u];  // 后续冲刺点深度必须 < limit
            
            // 对于每个可能的冲刺距离
            for (int k = min_k; k <= max_k; k++) {
                int anc = kth_ancestor(u, k);
                if (anc == 0) continue;
                
                // 检查深度限制
                if (depth[anc] < limit) {
                    // 从anc继续，但后续冲刺点深度必须 < min(limit, depth[anc] - h[anc])
                    // 简化：假设从anc继续的路径都满足限制
                    ans[u] = (ans[u] + ans[anc]) % MOD;
                } else if (anc == 1 && 0 < limit) {
                    // 直接到山顶
                    ans[u] = (ans[u] + 1) % MOD;
                }
            }
            
            // 直接冲刺到山顶
            if (depth[u] >= l[u] && depth[u] <= r[u]) {
                ans[u] = (ans[u] + 1) % MOD;
            }
        }
    }
    
    // 清理
    for (int d = 0; d <= max_depth; d++) {
        free(depth_nodes[d]);
    }
    free(depth_nodes);
    free(depth_cnt);
}

int main() {
    freopen("mountain.in", "r", stdin);
    freopen("mountain.out", "w", stdout);
    
    int c, t;
    scanf("%d %d", &c, &t);
    
    while (t--) {
        scanf("%d", &n);
        
        // 初始化
        ecnt = 0;
        memset(head, 0, sizeof(head));
        memset(ans, 0, sizeof(ans));
        
        // 读取输入
        for (int i = 2; i <= n; i++) {
            scanf("%d %d %d %d", &parent[i], &l[i], &r[i], &h[i]);
            add_edge(parent[i], i);
        }
        
        // 解决问题
        solve();
        
        // 输出结果
        for (int i = 2; i <= n; i++) {
            printf("%lld ", ans[i] % MOD);
        }
        printf("\n");
    }
    
    return 0;
}

算法详解

核心思想

1. 自底向上DP：从深度大的节点向深度小的节点计算
2. 状态转移：
   • 休息操作：$ans[i] += \sum_{j \in children(i)} ans[j]$
   • 冲刺操作：对于每个 $k \in [l_i, r_i]$：
     • 找到 $k$ 级祖先 $anc$
     • 如果 $depth[anc] < depth[i] - h_i$，则 $ans[i] += ans[anc]$
     • 如果 $anc = 1$ 且满足深度限制，则 $ans[i] += 1$（直接到山顶）
   • 直接冲刺到山顶：如果 $depth[i] \in [l_i, r_i]$，则 $ans[i] += 1$

时间复杂度

• 倍增求祖先：$O(\log n)$
• 对于每个点，枚举冲刺距离 $k$：最坏 $O(r_i - l_i)$
• 总复杂度：$O(n \cdot \text{平均冲刺范围长度} \cdot \log n)$

对于大数据，这可能会超时，需要进一步优化。

进一步优化建议

1. 前缀和优化：对于冲刺操作，我们实际需要的是：

   $$\sum_{k=l_i}^{r_i} [depth[anc(i,k)] < depth[i] - h_i] \cdot ans[anc(i,k)] $$

   可以预处理每个点的祖先序列，并使用前缀和快速计算区间和。

2. 深度限制优化：对于深度限制 $limit = depth[i] - h_i$，我们只需要考虑深度 $< limit$ 的祖先。

3. 记忆化搜索：使用记忆化避免重复计算。

这个版本将冲刺操作的复杂度从 $O((r_i - l_i) \log n)$ 降到了 $O(r_i - l_i)$，并且避免了多次调用 kth_ancestor 函数。

总结

这道题的关键在于理解深度限制 $h_i$ 的含义，并在状态转移中正确处理。通过自底向上的树形DP，结合适当的优化技巧，可以在合理的时间内解决问题。对于大数据范围，需要进一步优化冲刺操作的查询效率。