讲解 P10789 [NOI2024] 登山。

首先使用朴素的动态规划，前缀和优化到平方，考虑特殊性质的部分分，使用树剖进行优化，由特殊性质推到整体，使用主席树再次进行优化，中间需要多次倍增跳跃。

思路：

我们可以对于每个 \(i\) 找到它能跳到的最远的点和最近的点，倍增求一下 \(k\) 级祖先即可，令 \([l_i,r_i]\) 新表示 \(i\) 能跳到其祖先中深度在 \([l_i,r_i]\) 内的点；同时令 \(lim_i = d_i - h_i-1\) 表示 \(i\) 至少要跳到 \(lim_i\) 的深度。

考虑动态规划算法，令 \(dp_i\) 表示从 \(i\) 出发到山顶的合法登山序列个数。

那么相当于先从 \(i\) 滑落到 \(j\)，然后再从 \(j\) 冲刺到 \(k\)，再加上 \(dp_k\) 的方案数。

则状态转移方程为：

\[dp_i = \sum_{j 在 i 子树内} \sum_{k 为 i 的祖先} (d_k \in [l_j,\min(W(i,j),r_j)]) dp_k

\]

其中 \(W(i,j)\) 表示 \(i \to j\) 路径上 \(lim_k\) 的最小值，因为每次冲刺到达的深度必须小于所有经过的点的 \(lim_k\)。

朴素实现是 \(O(N^3)\) 的，考虑优化；注意到 \(k\) 是 \(i\) 的祖先中一段深度连续的点，则我们可以做一个深度的 \(dp_i\) 的前缀和，差分即可，时间复杂度优化至 \(O(N^2)\)，可以得到 25pts。

设 \(u^k\) 表示 \(u\) 的 \(k\) 级祖先，

现在考虑 \(l_j=r_j\) 的特殊性质，注意到对于 \(i\) 子树内的点 \(j\)，它最多只会对 \(dp_i\) 造成 \(dp_{j^{l_j}}\) 的贡献，注意到当 \(W(i,j) < r_j\) 时是没有贡献的。

则我们考虑枚举 \(j\)，且注意到随着 \(i\) 的深度的变小 \(W(i,j)\) 也会变小，考虑求出 \(g_j\) 表示深度最小的使得 \(W(g_j,j) \ge r_j\) 的点，直接倍增求即可。

那么对于 \(j \to g_j\) 路径上的 \(i\) 点，是可以由 \(i\) 下滑到 \(j\) 后冲刺到 \(j^{l_j}\) 的，那么对于 \(j \to g_j\) 路径上的 \(dp_i\) 的值都会增加 \(dp_{j^{l_j}}\)。

按照 \(j^{l_j}\) 的深度从小到大依次处理即可。

需要维护路径加，单点查，可以直接树剖与树状数组或线段树，时间复杂度为 \(O(N \log^2 N)\)，这样我们就拿到了 45pts。

现在考虑根据 \(l_j=r_j\) 的思路，求 \(l_j \ne r_j\) 的情况。

还是一样，枚举 \(j\)，则对于一个 \(i\) 会增加 \(s_{\min(r_j,W(i,j))}-s_{l_j-1}\) 的贡献，其中 \(s_u\) 在 \(j\) 的祖先链上，表示深度为 \(1 \sim u\) 的点的 \(dp\) 值。

考虑分开计算，发现对于 \(-s_{l_j-1}\) 的部分，就是 \(l_j=r_j\) 的情况，倍增求出深度最小的点 \(i\) 使得 \(W(i,j) \ge l_j\)，然后对于 \(i \to j\) 路径上的点都增加 \(-s_{l_j-1}\) 的贡献。

现在是如何处理 \(s_{\min(r_j,W(i,j))}\) 的部分，注意到肯定还是先取一段 \(r_j\)，同样枚举 \(j\)，倍增找到深度最小的满足 \(W(i,j) > r_j\)（注意是 \(>\)） 的 \(i\)，则对于 \(j \to i\) 路径上的 \(dp\) 值，都要增加 \(s_{r_j}\)。

然后考虑处理 \(s_{W(i,j)}\) 的情况，考虑枚举 \(u\)，使得 \(lim_u\) 是 \(i \to j\) 的严格后缀最小值（即最小值中深度最深的那个点），注意到我们只需要求出 \(u\) 子树内有多少个 \(j\) 满足 \(u \to j\) 的路径中没有小于等于 \(lim_u\) 的 \(lim_k\)，且 \(lim_u \in [l_j,r_j]\)。

只要求出了这样的 \(j\) 的个数 \(sum\)，则可以倍增求出深度最小的 \(i\) 使得 \(W(i,u) = lim_u\)，那么直接对于 \(i \to u\) 的路径上的点，都会增加 \(s_{lim_u} \times sum\) 的贡献。

注意到这样操作会有先后顺序的问题，考虑再求出 \(s_x\) 时，才考虑 \(l_j-1=x\) 和 \(r_j = x\) 和 \(lim_u=x\) 的贡献。

这样的话操作都是一些基本操作，链加，链查，倍增优化等，唯一需要注意的是查询 \(u\) 子树内有多少个 \(j\) 满足 \(u \to j\) 的路径中没有小于等于 \(lim_u\) 的 \(lim_k\)，且 \(lim_u \in [l_j,r_j]\)。

考虑对于 \(i\) 找到 \(i \to 1\) 的路径上第一个满足 \(lim_j < lim_i\) 的 \(j\)，那么令 \(Fa_i = j\)。

根据这个 \(Fa\)，建出边为 \(i \to Fa_i\) 的新树，那么上述询问就变为了在求新树中 \(u\) 子树内的点 \(j\) 满足 \(lim_u \in [l_j,r_j]\) 的个数，证明显然，不再阐述。

那么可以每次将 \([l_j,r_j]\) 范围内的 \(sum_i\) 增加 \(1\)，那么满足条件的数的数量就是 \(sum_{lim_u}\)。

考虑对于新树求出 dfn 序，则 \(u\) 子树内的点可以算作一段区间 \([L,R]\)，然后建出前缀主席树即可快速求 \(lim_u\) 被区间包含的个数（因为要区间加，可以直接标记永久化）。

也可以使用 dsu on tree 做，但是本人太菜不会。

总时间复杂度为 \(O(N \log^2 N)\)。

注意主席树的空间要开 \(50\) 倍。

完整代码；

#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

#define For(i,l,r) for(int i=l;i<=r;i++)

#define _For(i,l,r) for(int i=r;i>=l;i--)

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

const ll N=1e5+10,M=20,mod=998244353,INF=1e9;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

int T,n;

int root[N],fa[N],l[N],r[N],h[N],id[N],_id[N],dfn[N];

vector<int> E[N],G[N];

inline void add(int u,int v){

E[u].push_back(v);

E[v].push_back(u);

}

inline void ADD(int u,int v){

G[u].push_back(v);

G[v].push_back(u);

}

inline void Read(){

n=read();

For(i,1,n){

E[i].clear();

G[i].clear();

}

For(i,2,n){

fa[i]=read(),l[i]=read(),r[i]=read(),h[i]=read();

add(fa[i],i);

}

}

class Tree{

public:

int cnt=0;

int p[N],t[N],z[N],d[N],fa[N];

struct Node{

int l,r,len;

ll data;

ll tag;

}X[N<<2];

inline void dfs1(int u,int f){

p[u]=1;

for(auto v:E[u]){

if(v==f)

continue;

d[v]=d[u]+1;

fa[v]=u;

dfs1(v,u);

p[u]+=p[v];

if(p[v]>p[z[u]])

z[u]=v;

}

}

inline void dfs2(int u,int k){

dfn[u]=++cnt;

t[u]=k;

if(!z[u])

return ;

dfs2(z[u],k);

for(auto v:E[u]){

if(v==fa[u]||v==z[u])

continue;

dfs2(v,v);

}

}

inline void build(int k,int l,int r){

X[k].len=r-l+1;

X[k].l=l,X[k].r=r;

X[k].data=X[k].tag=0;

if(l==r)

return ;

int mid=(l+r)>>1;

build(k<<1,l,mid);

build(k<<1|1,mid+1,r);

}

inline void pushup(int k){

X[k].data=Add(X[k<<1].data,X[k<<1|1].data);

}

inline void add(int k,int v){

X[k].data=(X[k].data+1ll*X[k].len*v%mod)%mod;

X[k].tag=Add(X[k].tag,v);

}

inline void push_down(int k){

if(X[k].tag){

add(k<<1,X[k].tag);

add(k<<1|1,X[k].tag);

X[k].tag=0;

}

}

inline void update(int k,int l,int r,int v){

if(X[k].l==l&&r==X[k].r){

add(k,v);

return ;

}

push_down(k);

int mid=(X[k].l+X[k].r)>>1;

if(r<=mid)

update(k<<1,l,r,v);

else if(l>mid)

update(k<<1|1,l,r,v);

else{

update(k<<1,l,mid,v);

update(k<<1|1,mid+1,r,v);

}

pushup(k);

}

inline int query(int k,int l,int r){

if(X[k].l==l&&r==X[k].r)

return X[k].data;

push_down(k);

ll mid=(X[k].l+X[k].r)>>1;

if(r<=mid)

return query(k<<1,l,r);

else if(l>mid)

return query(k<<1|1,l,r);

else

return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%mod;

}

inline int query(int k,int i){

if(X[k].l==i&&i==X[k].r)

return X[k].data;

push_down(k);

ll mid=(X[k].l+X[k].r)>>1;

if(i<=mid)

return query(k<<1,i);

else

return query(k<<1|1,i);

}

inline void update(int u,int v,int h){

while(t[u]!=t[v]){

if(d[t[u]]<d[t[v]])

swap(u,v);

update(1,dfn[t[u]],dfn[u],h);

u=fa[t[u]];

}

if(d[u]>d[v])

swap(u,v);

update(1,dfn[u],dfn[v],h);

}

inline int ask(int u,int v){

int ans=0;

while(t[u]!=t[v]){

if(d[t[u]]<d[t[v]])

swap(u,v);

ans=(ans+query(1,dfn[t[u]],dfn[u]))%mod;

u=fa[t[u]];

}

if(d[u]>d[v])

swap(u,v);

ans=(ans+query(1,dfn[u],dfn[v]))%mod;

return ans;

}

inline void init(){

For(i,1,n)

z[i]=0;

cnt=0;

dfs1(1,1);

dfs2(1,1);

build(1,1,n);

}

}Tr;

namespace Seg{

int siz[N];

int cnt,s;

struct Node{

int L,R;

int tag;

}X[N*50];

inline void dfs(int u,int fa){

id[u]=++s;

_id[s]=u;

siz[u]=1;

for(auto v:G[u]){

if(v==fa)

continue;

dfs(v,u);

siz[u]+=siz[v];

}

}

inline void tidy(){

For(i,1,cnt)

X[i]={0,0,0};

s=cnt=0;

dfs(1,1);

}

inline void build(int &k,int l,int r){

if(!k)

k=++cnt;

X[k].tag=0;

if(l==r)

return ;

int mid=(l+r)>>1;

build(X[k].L,l,mid);

build(X[k].R,mid+1,r);

}

inline void update(int &k,int l,int r,int L,int R,int v){

X[++cnt]=X[k];

k=cnt;

if(l==L&&r==R){

X[k].tag=Add(X[k].tag,v);

return ;

}

ll mid=(l+r)>>1;

if(R<=mid)

update(X[k].L,l,mid,L,R,v);

else if(L>mid)

update(X[k].R,mid+1,r,L,R,v);

else{

update(X[k].L,l,mid,L,mid,v);

update(X[k].R,mid+1,r,mid+1,R,v);

}

}

inline void Ask(int k,int l,int r,int i,int &ans){

ans=Add(ans,X[k].tag);

if(l==i&&i==r)

return ;

int mid=(l+r)>>1;

if(i<=mid)

Ask(X[k].L,l,mid,i,ans);

else

Ask(X[k].R,mid+1,r,i,ans);

}

inline int Ask(int u){

int X=0,Y=0;

Ask(root[id[u]+siz[u]-1],0,n,h[u],X);

Ask(root[id[u]-1],0,n,h[u],Y);

return (X-Y+mod)%mod;

}

};

namespace Std{

int Min,sum,x,a,b,c,t;

int dep[N],g1[N],g2[N],g3[N];

int Fa[N][M],F[N][M];

vector<pi> E1[N],E2[N],E3[N];

inline void dfs(int u){

For(j,1,M-1)

Fa[u][j]=Fa[Fa[u][j-1]][j-1];

for(auto v:E[u]){

if(v==fa[u])

continue;

Fa[v][0]=u;

dep[v]=dep[u]+1;

dfs(v);

}

}

inline int get_fa(int u,int k){

if(!k)

return u;

_For(j,0,M-1){

if(k>=(1ll<<j)){

k-=(1ll<<j);

u=Fa[u][j];

}

}

return u;

}

inline void dfs1(int u){

For(i,1,M-1)

F[u][i]=min(F[u][i-1],F[Fa[u][i-1]][i-1]);

for(auto v:E[u]){

if(v==fa[u])

continue;

F[v][0]=h[v];

dfs1(v);

}

}

inline void solve(){

Read();

For(j,0,M-1)

Fa[1][j]=1;

dfs(1);

For(i,1,n)

root[i]=0;

For(i,0,n-1){

E1[i].clear();

E2[i].clear();

E3[i].clear();

}

For(i,2,n){

a=get_fa(i,r[i]),b=get_fa(i,l[i]),c=get_fa(i,h[i]+1);

h[i]=dep[i]-h[i]-1;

l[i]=dep[a],r[i]=dep[b];

if(l[i])

E1[l[i]-1].push_back({i,fa[a]});

E2[r[i]].push_back({i,b});

E3[h[i]].push_back({i,c});

}

For(j,0,M-1)

F[1][j]=INF;

dfs1(1);

For(i,2,n){

if(l[i]){

x=i;

_For(j,0,M-1)

if(F[x][j]>=l[i])

x=Fa[x][j];

if(x==i)

g1[i]=-1;

else

g1[i]=get_fa(i,dep[i]-dep[x]-1);

}

else

g1[i]=-1;

x=i;

_For(j,0,M-1)

if(F[x][j]>r[i])

x=Fa[x][j];

if(x==i)

g2[i]=-1;

else

g2[i]=get_fa(i,dep[i]-dep[x]-1);

Min=INF,x=i;

_For(j,0,M-1)

if(F[x][j]>=h[i])

x=Fa[x][j];

ADD(i,x);

if(x==i)

g3[i]=-1;

else

g3[i]=get_fa(i,dep[i]-dep[x]-1);

}

Tr.init();

Tr.update(1,1,1);

Seg::tidy();

Seg::build(root[1],0,n);

For(i,2,n){

root[i]=root[i-1];

Seg::update(root[i],0,n,l[_id[i]],r[_id[i]],1);

a=0;

Seg::Ask(root[i],0,n,0,a);

}

For(i,0,n-1){

for(auto t:E1[i]){

x=t.fi,b=g1[x];

if(b==-1)

continue;

a=Tr.ask(1,t.se);

Tr.update(x,b,mod-a);

}

for(auto t:E2[i]){

x=t.fi,b=g2[x];

if(b==-1)

continue;

a=Tr.ask(1,t.se);

Tr.update(x,b,a);

}

for(auto t:E3[i]){

x=t.fi,b=g3[x];

if(b==-1)

continue;

a=Tr.ask(1,t.se);

sum=Seg::Ask(x);

Tr.update(x,b,1ll*sum*a%mod);

}

}

For(i,2,n){

write(Tr.query(1,dfn[i]));

putchar(' ');

}

putchar('\n');

}

inline void work(){

while(T--)

solve();

}

};

int main(){

//open("A.in","A.out");

read(),T=read();

Std::work();

return 0;

}