You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

树上旅行

题目描述

Zzzyt在一棵$n$个节点的有根树上旅行，初始时在根节点。他在每个节点需停留至少一天，然后可以选择花费一定天数到达其中一个子节点，或结束旅行。同时，他要求整个旅行过程不超过$m$天。那么，有多少种不同的旅行方案？两种方案不同，当且仅当经过的节点不同或在同一节点停留的时间不同。

输入格式

第一行两个整数$n$,$m$。

接下来$n-1$行，其中第$i$行两个整数$f_i$，$w_i$，表示第$i+1$号节点的父节点为$f_i$，从父节点到第$i+1$号节点需要$w_i$天。

$1$号节点为根节点。

输出格式

一个整数，表示可能的旅行方案数，对$998244353$取模。

输入输出样例

3 5
1 1
1 2

14

5 100000
1 0
2 0
3 0
4 0

686855603

数据规模与约定

$1 \leq n,m \leq 10^5$

$0 \leq w_i \leq 10^5$

$1 \leq f_i \leq n$