传送门

首先状态是简单的：$f_x$ 表示从 $x$ 出发到达山顶的方案数。

在题目的限制下显然是无后效性的。

做一个树上前缀和，设 $y$ 到 $x$ 路径上 $d-h$ 的最小值为 $k$，则贡献是形如 $g_{\min\{r_y,k\}}-g_{l_y}$ 的式子。

可以发现，从下往上做是相对容易的。

考虑从下往上做，再从上往下撤销。

当前 dfs 到一个位置，用并查集维护其子树内的点到这个点路径上 $d-h$ 的最值。

具体地，$y$ 到当前根的最值在 $y$ 所在的集合的代表元处取到。

倍增预处理一个点上面第一个 $d-h$ 小于这个点的位置，直接合并即可。

可以给每个点开个 vector，存储的信息形如 $l_i,r_i,k_i$，表示这个点的 dp 值等于 $\sum k_i(g_{r_i}-g_{l_i-1})$，这样方便直接撤销。

启发式合并即可做到 $O(n\log n)$。

还要特殊处理 $l>r$ 的情况，对每个点倍增找到贡献为 $0$ 的位置，直接打个 tag 即可。

总复杂度 $O(n\log n)$，数据结构仅需要用到并查集。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5,mods=998244353;
int op,t,n,nw,fa[N],l[N],dy[N],r[N],mk[N],sm[N],sz[N],h[N],ff[N],d[N],f[N],dp[N],f1[N][20],f2[N][20];
vector<int>p[N],g[N],q[N],jl[N];
struct node{
	int l,r,op;
};
vector<node>fs[N];
int fd(int x){
	if(x==ff[x])return x;
	return ff[x]=fd(ff[x]);
}
void dfs(int x){
	for(int i=1;i<=18;i++){
		f1[x][i]=f1[f1[x][i-1]][i-1];
		f2[x][i]=min(f2[x][i-1],f2[f1[x][i-1]][i-1]);
	}
	h[x]=d[x]-h[x]-1;
	l[x]=d[x]-l[x];
	r[x]=d[x]-r[x];
	swap(l[x],r[x]);
	int y=x;
	for(int i=18;i>=0;i--)if(f2[y][i]>=h[x])y=f1[y][i];
	g[fa[y]].push_back(x);
	y=x;
	for(int i=18;i>=0;i--)if(f2[y][i]>=l[x])y=f1[y][i];
	if(h[x]>=l[x])jl[fa[y]].push_back(x);
	else jl[x].push_back(x);
	y=x;
	for(int i=18;i>=0;i--)if(f2[y][i]>=r[x])y=f1[y][i];
	if(h[x]>=r[x])q[fa[y]].push_back(x);
	else q[x].push_back(x);
	for(auto c:p[x]){
		d[c]=d[x]+1;
		f1[c][0]=x;
		f2[c][0]=h[x];
		dfs(c);
	}
}
void init(int x){
	for(auto c:p[x])init(c);
	sort(p[x].begin(),p[x].end(),[&](int a,int b){
	    return fs[a].size()>fs[b].size();
	});
	if(p[x].size())swap(fs[x],fs[p[x][0]]);
	for(int i=1;i<p[x].size();i++){
		int c=p[x][i];
		for(auto d:fs[c])fs[x].push_back(d),sm[x]++;
	}
	fs[x].push_back({l[x],r[x],1});
	sm[x]++;
	for(auto c:q[x]){
		fs[x].push_back({l[c],r[c],-1});
		fs[x].push_back({l[c],h[x],1});
		dy[c]=x;
		sz[x]++;
		sm[x]+=2;
	}
	for(auto c:jl[x]){
		fs[x].push_back({l[c],h[fd(dy[c])],-1});
		sz[fd(dy[c])]--;
		sm[x]++;
	}
	for(auto c:g[x]){
		fs[x].push_back({h[x]+1,h[c],-sz[c]});
		sz[x]+=sz[c];
		ff[c]=x;
		sm[x]++;
	}
}
int gets(int l,int r){
	if(l>nw)return 0;
	if(l>r)return 0;
	return dp[min(r,nw)]-dp[l-1];
}
void solve(int x,int res){
	if(mk[x])for(auto c:fs[x])res+=gets(c.l,c.r)*c.op,res%=mods;
	if(x!=1)f[x]=res;
	dp[d[x]]=(dp[d[x]-1]+f[x])%mods;
	nw=d[x];
	while(sm[x]--){
		auto c=fs[x].back();
		fs[x].pop_back();
		res-=gets(c.l,c.r)*c.op;
		res%=mods;
	}
    if(p[x].size()){
    	swap(fs[x],fs[p[x][0]]);
    	solve(p[x][0],res);
    	for(int i=1;i<p[x].size();i++){
    		int c=p[x][i];
    		mk[c]=1;
    		nw=d[x];
    		solve(c,0);
    	}
    }
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>op>>t;
	while(t--){
		memset(f,0,sizeof(f));
		memset(f1,0,sizeof(f1));
		memset(f2,0x3f,sizeof(f2));
		cin>>n;	
		for(int i=1;i<=n;i++)ff[i]=i,mk[i]=0,sm[i]=0,sz[i]=0,p[i].clear(),g[i].clear(),fs[i].clear(),q[i].clear(),jl[i].clear();
		for(int i=2;i<=n;i++){
			cin>>fa[i]>>l[i]>>r[i]>>h[i];
			p[fa[i]].push_back(i);
		}
		d[1]=1;
		dfs(1);
		init(1);
		f[1]=1;
		solve(1,0);
		for(int i=2;i<=n;i++)cout<<(f[i]%mods+mods)%mods<<" ";
		cout<<"\n";
	}
}

2026.4.22：又自己重新做了一下这道好题，再补个题解。今年终于可以打 NOI 了。

先理一下限制。

我们记一次攀登为这个过程：$i$ 是某次冲刺过后的位置。从 $i$ 开始休息若干次（可能为 $0$ 次），滑落到 $j$，然后再从 $j$ 冲刺一次到达 $k$。不难发现两次攀登的限制是独立的。这里可以做到 $O(n^3)$。

然后理一下这个转移的限制：

• $i$ 是 $j$ 的祖先，$k$ 是 $i$ 的祖先。
• $l_j\le d_j-d_k\le r_j$。
• $d_k<\min_{l\in \mathrm{path}(i,j)} (d_l-h_l)$。

再改一下第二个限制，那么对于 $d_k$ 有限制 $d_j-r_j\le d_k\le d_j-l_j$，然后又有 $d_k\le \min_{l\in \mathrm{path}(i,j)} (d_l-h_l-1)$。

那么有一个限制是和 $j$ 有关的，有另外一个限制是和 $i,j$ 都有关的，考虑先固定 $j$。

分类讨论 $\min_{l \in \mathrm{path}(i,j)}(d_l-h_l-1)$ 和 $d_j-l_j$ 的大小关系。

Case 1

假设 $\min_{l \in \mathrm{path}(i,j)}(d_l-h_l-1)\ge d_j-l_j$，找到最小的 $d_i$ 满足这个条件，记为 $F_j$ 表示这样找到的 $i$。

那么 $j$ 可以帮助 $j$ 的 $l_j\sim r_j$ 级祖先转移到 $j\sim F_j$ 这些点。在 $l_j$ 这个点的 $dp$ 值算完以后找到 $j\sim F_j$ 这条链即可。

Case 2

假设 $d_j-r_j\le \min_{l \in \mathrm{path}(i,j)}(d_l-h_l-1)< d_j-l_j$。

这个情况看起来就比较复杂，而且在变 $i$ 的同时改变贡献范围，看起来有点魔怔。

这个 case 中 $dp_i$ 被 $s_{L}-s_{R}$ 贡献了，$s_i$ 是 $dp_i$ 到根的前缀和。$L$ 和 $R$ 具体是什么不重要，但是 $R$ 是固定的，所以我们可以先扔掉 $s_R$。

那么现在一对 $(i,j)$ 的贡献：

• 首先要求 $i$ 是 $F_j$ 的严格祖先，并且 $H_j$ 是 $i$ 的祖先。$H_j$ 是什么不用管。
• 此外，$j$ 的 $\min_{l \in \mathrm{path}(i,j)}(d_l-h_l-1)$ 级祖先的 $s$ 值是这次贡献的系数。

想一下这是啥意思啊。区间 $\min$ 的形态让我们想到一点笛卡尔树，枚举了几个做法以后发现我们应该让 $(i\sim j)$ 的最小值和这个最小值所在的最浅位置 $p$ 挂钩，具体的：

• 一个点 $u$ 有 $fa_u$ 表示 $u$ 的祖先中，第一个比 $u$ 小的数。记这棵树为 $T_{fa}$。
• $i\sim j$ 的最小值是 $j$ 一直往上跳后跳到的结果。

考虑 $fa_u\sim u$ 这个路径上（不含 $fa_u$）的点 $i$，都可以被 $u$ 在 $T_{fa}$ 树上的子树贡献。

预处理一下子树大小，就可以在 $fa_u$ 的祖先的 $dp$ 值都被算完后，立刻给 $fa_u\sim u$ 都贡献上 $u$ 的 $d_u-h_u-1$ 的贡献，并乘上合法的 $j$ 的数量。

这个数量是多少？$j$ 对 $i$ 的限制可以简单的看成深度限制，预处理 $T_{fa}$ 子树内的数据结构，查一次即可。

Case 3

假设 $\min_{l \in \mathrm{path}(i,j)}(d_l-h_l-1)< d_j-r_j$。

这个大家应该都会做。

总结

树链加法可以树上差分，拆成单点加，子树查。

时间复杂度 $O(n\log n)$。

---

下面是 2024.7.25 通过的题解：

免责声明：场外选手纯凑热闹。我只是一个 CSP-S 2= 的准退役选手别骂我呜呜呜，从描述就可以看出作者可能会讲的比较初等，请见谅。

“为什么要攀登？因为山就在那里。”

下文定义 $\displaystyle s_i = d_i - h_i - 1,p_{i,j}=\min_{k \in \mathrm{path}_{i,j}}s_k$。

设 $f_i$ 为点 $i$ 到山顶的方案数。简单分析一下，可以发现肯定是先向下走一段距离到一个点 $j$，再突然跳到一个 $j$ 的祖先（由题目的另一个描述可以知道这同样是 $i$ 的祖先）$k$ 上。一路上经过了 $i$ 到 $j$ 路径上的所有点还有 $k$ 点。有图为证：

我们为了求出 $f_i$，需要用 $f_k$ 贡献。仔细读题后发现，$k$ 的两个条件都比较强，一个是 $d_j-r_j \leq d_k \le d_j-l_j$，另一个是 $d_k \leq p_{i,j}$。

但是我们发现这两个条件都和 $j$ 有关，而且根据一大堆题目的经验，我们从 $j$ 点开始考虑。

计算出每一个点到根节点的 $f$ 的总和 $g$。因为 $k$ 是 $i$ 的祖先上的一个区间，所以采用前缀和，要加在 $f_i$ 上的答案变为 $g_{\min(d_j-l_j,p_{i,j})}-g_{d_j-r_j-1}$。

分类讨论点 $i$ 的位置。

如图，红点是不能被算入贡献（$p_{i,j}<d_j-r_j$）的，黄点是 $p_{i,j} < d_j-l_j$ 的。绿点是 $p_{i,j} \ge d_j -l_j$ 的。可以发现红黄绿三种点一定是如图排列的。

$-g_{d_j-r_j-1}$ 的贡献，用倍增找到黄绿点以后可以直接链加上去。下文考虑 $g_{\min(d_j-l_j,p_{i,j})}$。

绿点很好处理，用倍增找到以后可以直接链加上去。

黄点比较难。考虑枚举从 $j$ 到 $i$，前缀最小值的位置（如果有多个请取深度最大的那个）$x$，请观察以下的图片（由一条链沿着叶子到根的方向拍下来）。

其中，$j$ 会一直到一个比当前这个前缀最小值更小的位置（但是，不能越过绿点的界线，也就是 $d_j-l_j > h_x$）。$i$ 点同理。所以，我们可以随便用数据结构维护 $j$ 的个数，然后直接链加到每个 $i$ 上。

这里有许多的链加操作，事实上不需要树链剖分，只需要差分一下然后查询的时候查子树和就可以了。用 dfs 序，写一个树状数组即可。

另外有一个细节就是因为我们不能等枚举到 $j$ 了才做这些操作（因为 $i$ 是 $j$ 的祖先）。所以我们要把 $j$ 的每一个限制（$d_j-r_j,d_j-l_j$）给离线，然后当 $k$ 的数据算出时立马贡献。当然，前缀最小值 $x$ 同理。

总结：很厉害，学到了很多。

但是作者太菜了，而且怕给其他人带来不便，所以不放代码了。

本题解参考了其他题解，主要用于自己总结用，并且另外补充了一下图解。