登山 NOI2024

[NOI2024] 登山

这是第一个我自己写出来的树形 DP 黑题。

题目链接： [NOI2024] 登山 。

题目描述：

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

慕士塔格山上有 nn 处点位，点从 11 到 nn 编号，11 号点位为山顶。这 nn 个点位构成一棵有根树的结构，其中 11 号点位为根，对于 2≤i≤n2\leq i\leq n，ii 号点位的父亲结点为 pip_i 号点位。

记 did_i 为 ii 号点位到山顶所需经过的边数。形式化地说，d1=0d_1=0，对于 2≤i≤n2\leq i\leq n，di=dpi+1d_i=d_{p_i}+1。

定义一条登山路径为从 2∼n2\sim n 号点位中的某一个开始，经过若干次移动后到达山顶的方案。

定义一次从 i(2≤i≤n)i(2\leq i\leq n) 号点位出发的移动为以下两种方式之一：

  1. 冲刺：在给定的冲刺范围 [li,ri][l_i,r_i] 内，选择一个正整数 kk 满足 li≤k≤ril_i\leq k\leq r_i，向山顶移动 kk 步，即移动至 ii 号点位在有根树上的 kk 级父亲处。保证 1≤li≤ri≤di1\leq l_i\leq r_i\leq d_i。
  2. 休息：由于慕士塔格山地形陡峭，休息时会滑落到某一个儿子结点处。形式化地说，选择一个满足 pj=ip_j=i 的 jj，移动至到 jj 号点位。特别地，若 ii 号点位为有根树的叶子结点，则不存在满足 pj=ip_j=i 的 jj，因此此时不能选择休息。

定义一条登山路径对应的登山序列为初始点位以及每次移动到的点位所构成的序列。形式化地说，一条从 xx 号点位开始的登山路径对应的登山序列是一个点序列 a1=x,a2,…,am=1a_1=x,a_2,\dots,a_m=1 满足对于 1≤i<m1\leq i<m，ai+1a_{i+1} 是 aia_i 的 k(lai≤k≤rai)k(l_{a_i}\leq k\leq r_{a_i}) 级祖先或 pai+1=aip_{a_{i+1}}=a_i。

为了保证每次冲刺都能更接近山顶，一条合法的登山路径需要满足：对于初始点位或某次移动到的点位 ii，以后冲刺到的点位 jj 都必须满足 dj<di−hid_j<d_i-h_i，其中 hih_i 是一个给定的参数，保证 0≤hi<di0\leq h_i<d_i。形式化地说，一条合法的登山路径对应的登山序列 a1,a2,…,ama_1,a_2,\dots,a_m 需要满足：对于所有 1≤i<j≤m1\leq i<j\leq m，若 paj≠aj−1p_{a_j} \neq a_{j-1}，则 daj<dai−haid_{a_j}<d_{a_i}-h_{a_i}。

对于 2∼n2\sim n 号所有点位，求从这些点位开始的合法的登山路径条数。两条登山路径不同当且仅当其对应的登山序列不同。由于答案可能较大，你只需要求出答案对 998 244 353998\,244\,353 取模后的结果。

对于所有测试数据保证：1≤t≤41\leq t\leq 4，2≤n≤1052\leq n\leq 10^5。

对于任意的 2≤i≤n2\leq i\leq n，保证：1≤pi<i1\leq p_i<i，1≤li≤ri≤di1\leq l_i\leq r_i\leq d_i，0≤hi<di0\leq h_i<d_i。

测试点编号 n≤n\leq 是否有 li=ril_i=r_i 是否有 hi=0h_i=0 是否有 pi=i−1p_i=i-1
11 66 否 否 否
2,32,3 300300 ^ ^ ^
4,54,5 50005000 ^ ^ ^
66 10510^5 是 是 是
77 ^ ^ ^ 否
88 ^ ^ 否 是
99 ^ ^ ^ 否
1010 ^ 否 是 是
11,1211,12 ^ ^ ^ 否
1313 ^ ^ 否 是
14∼2014\sim 20 ^ ^ ^ 否

观察题目,可以发现这是一个计数题目，并且这题目还在树上，那么我们就只有树形 DP 这一个解决方案了。

15pts15pts ：暴力树形 DP

有些题目，像这题，即使是最朴素的暴力 DP 也很难想。

首先，这个题目的决策点是树上的每个点，而决策是选择休息或冲刺。

那么自然可以得出第一个状态设计： fif_i 表示 ii 冲向 11 的方案数。

那么按照决策，分两种情况：

  1. 冲刺。这种情况下需要冲刺到 [max⁡{li,hi+1},ri][\max\{l_i,h_i+1\},r_i] 级祖先。方案数为 ∑合法祖先FfF\sum\limits_{合法祖先 F}f_F 。
  2. 休息。这种情况需要累加所有儿子的方案数，即 ∑u∈sonifu\sum\limits_{u\in son_i}f_u 。但是由于有 hih_i 的限制，下一次冲刺必须冲刺到 di−hi−1d_i-h_i-1 及以上的位置，此时无法转移。

所以我们要加一维。定义 fi,jf_{i,j} 表示从节点 ii 出发，冲向 11 且下一次冲刺到深度 jj 的方案数。

设 ii 的深度为 jj 的祖先为 xx 。

接着按照决策，分三种情况：

  1. jj 不合法，即 di−hi≤jd_i-h_i\le j 。这种情况下 fi,j=0f_{i,j}=0 。
  2. 在 jj 合法时，冲刺。此时需要满足 di−ri≤j≤di−lid_i-r_i\le j\le d_i-l_i 。这种情况方案数为 ∑kfx,k\sum\limits_{k}f_{x,k} 。
  3. 在 jj 合法时，休息。此时可以滑落至任意一个儿子。这种情况的方案数为 ∑uu∈sonifu,j\sum\limits_{uu\in son_i}f_{u,j} 。

然后又会发现，这样转移似乎有后效性，因为一个点会从他的祖先和儿子同时转移而来。

但仔细想后就会发现，其实每个点只会从他的儿子转移，于是从下到上合并儿子转移就行。这是因为对于祖先的转移是 fx,k,k<jf_{x,k},k<j ，因为 xx 无法冲刺到它本身。

于是我们对着 jj 这一维顺序树形 DP 就行。

时间复杂度 O(n2log⁡n)O(n^2\log n) 。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
using namespace std;
const int N=5010,P=998244353;
int cid,T,n,f[N][N],d[N],F[N][16],sum[N],l[N],r[N],h[N];
vector<int>v[N];
void dfs(int x,int fa){
    F[x][0]=fa;
    d[x]=d[fa]+1;
    for(int i=1;i<=15;i++)F[x][i]=F[F[x][i-1]][i-1];
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
    }
}
int lca(int x,int k){
    for(int i=15;i>=0;i--)if((k>>i)&1)x=F[x][i];
    return x;
}
void dfs2(int x,int fa,int j){
    int tmp=0;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x,j);
        (tmp+=f[u][j])%=P;
    }
    if(d[x]-h[x]-1>=j){
        f[x][j]=tmp;
        if(d[x]-l[x]>=j&&j>=d[x]-r[x])(f[x][j]+=sum[lca(x,d[x]-j)])%=P;
    }
    (sum[x]+=f[x][j])%=P;
}
int main(){
    scanf("%d%d",&cid,&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)v[i].clear(),sum[i]=0;
        for(int i=2,x;i<=n;i++){
            scanf("%d%d%d%d",&x,l+i,r+i,h+i);
            v[x].push_back(i);
            v[i].push_back(x);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                f[i][j]=0;
        sum[1]=1;
        for(int i=1;i<=n;i++)dfs2(1,0,i);
        for(int i=2;i<=n;i++)printf("%d ",sum[i]);puts("");
    }
    return 0;
}

25pts25pts ：优化版暴力树形 DP

可以发现，在上面的代码对着 jj 转移时，所有可以冲刺到的点带来的贡献都是 sumxsum_x ， xx 是某个深度为 jj 的点。

也就是说，对于 xx 的祖先，他们的 DP 值都是 00 ，而对于 xx 子树内的点，他们的深度为 jj 的祖先都是 xx ，于是就可以把 kk 级祖先的 O(log⁡n)O(\log n) 去掉，复杂度变成 O(n2)O(n^2) 。

如果再想想就会发现，对于固定的 jj ， fi,jf_{i,j} 的转移只会用到 fu,jf_{u,j} 和 sumxsum_x ，于是可以把 jj 这一维压掉，空间由 O(n2)O(n^2) 优化至 O(n)O(n) 。

空间 O(n2)O(n^2) 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N=5010,P=998244353;
int cid,T,n,f[N][N],d[N],sum[N],l[N],r[N],h[N];
vector<int>v[N];
void dfs(int x,int fa){
    d[x]=d[fa]+1;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
    }
}
void dfs2(int x,int fa,int j,int rt){
    int tmp=0;
    if(d[x]==j)rt=x;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x,j,rt);
        (tmp+=f[u][j])%=P;
    }
    f[x][j]=0;
    if(d[x]-h[x]-1>=j){
        f[x][j]=tmp;
        if(d[x]-l[x]>=j&&j>=d[x]-r[x])(f[x][j]+=sum[rt])%=P;
    }
    (sum[x]+=f[x][j])%=P;
}
int main(){
    scanf("%d%d",&cid,&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)v[i].clear(),sum[i]=0;
        for(int i=2,x;i<=n;i++){
            scanf("%d%d%d%d",&x,l+i,r+i,h+i);
            v[x].push_back(i);
            v[i].push_back(x);
        }
        dfs(1,0);
        sum[1]=1;
        for(int i=1;i<=n;i++)dfs2(1,0,i,0);
        for(int i=2;i<=n;i++)printf("%d ",sum[i]);puts("");
    }
    return 0;
}

空间 O(n)O(n) 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
const int N=100010,P=998244353;
int cid,T,n,f[N],d[N],sum[N],l[N],r[N],h[N];
vector<int>v[N];
void dfs(int x,int fa){
    d[x]=d[fa]+1;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
    }
}
void dfs2(int x,int fa,int j,int rt){
    int tmp=0;
    if(d[x]==j)rt=x;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x,j,rt);
        (tmp+=f[u])%=P;
    }
    f[x]=0;
    if(d[x]-h[x]-1>=j){
        f[x]=tmp;
        if(d[x]-l[x]>=j&&j>=d[x]-r[x])(f[x]+=sum[rt])%=P;
    }
    (sum[x]+=f[x])%=P;
}
int main(){
    scanf("%d%d",&cid,&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)v[i].clear(),sum[i]=0;
        for(int i=2,x;i<=n;i++){
            scanf("%d%d%d%d",&x,l+i,r+i,h+i);
            v[x].push_back(i);
            v[i].push_back(x);
        }
        dfs(1,0);
        sum[1]=1;
        for(int i=1;i<=n;i++)dfs2(1,0,i,0);
        for(int i=2;i<=n;i++)printf("%d ",sum[i]);puts("");
    }
    return 0;
}

25pts25pts ：暴力线段树合并优化树形 DP

暴力部分结束了，接下来是优化 DP 。

首先，优化 DP 一般有两种：一种是改变状态优化，一种是利用 DP 的结构性质优化。

这个 DP 显然状态设计上无法优化，于是只能通过观察 DP 的结构性质。

一般的一个观察是抛弃 ff 数组，直接利用 DP 结构进行优化，但很可惜这是无法优化的（至少我没想到）。

错误的思路：

考虑刻画 DP 结构。容易发现这个 DP 的结构本质上是对于每个 jj ，每个 ii ，若 jj 对于 ii 合法且 ii 可以冲刺到 jj ，则找到最小深度的祖先 xx 满足 jj 对于 ii 到 xx 路径上的点合法，将路径上的点的 sumsum 累加上 ii 深度为 jj 的祖先 yy 的权值 sumysum_y 。

可惜到这一步为止了，无法进一步优化。

刻画 DP 结构本质是不可能了，只能找到一些可以优化的地方进行优化。

我们发现 fi,jf_{i,j} 转移时，会将子节点 uu 的 fu,jf_{u,j} 累加，这很像线段树合并。

进一步的，对于叶子节点，他们不能休息，只能冲刺。那么对于叶子 ii ， fi,jf_{i,j} 在一段区间里面有值。那么对于任意节点 ii ， ii 里面最多只有 sizisiz_i 个区间（可重叠）有值，这正好对应线段树区间加和区间合并。

这引导我们去线段树合并。

但是这样做又有一个问题：直接合并就不能按 jj 的顺序转移了，又有后效性了。

此时又需要一个极为 tricky 的想法（ How have I thought out this tricky method? ）：系数。

我们发现，对于 ii ，设他的深度 jj 的祖先为 xx ，那么对于任意一个 ii 子树内的节点 uu ， ii 必然由 uu 转移而来，同时 ii 和 uu 都有 xx 转移而来，即， fi,j=Ksumxf_{i,j}=Ksum_x 。

当我们不按照 jj 得顺序转移时，虽然我不能直接转移 fi,jf_{i,j} ，但是前面的那个系数 KK 与 xx 无关，可以不按照 jj 的顺序转移。那么我们就可以成功的线段树合并转移出系数。

对于每个点 ii ：

  1. 先累加 ii 自己的贡献，也就是 [di−ri,min⁡{di−hi−1,di−li}][d_i-r_i,\min\{d_i-h_i-1,d_i-l_i\}] 的位置，每个位置上的数 +1+1 。
  2. 然后区间合并儿子，具体就是只合并区间 [1,di−hi−1][1,d_i-h_i-1] 的位置。

这里面还有一个小细节，就是线段树合并不好处理区间加，这里可以用差分代替。但是注意，由于 fi,jf_{i,j} 有值的地方仅限于 [1,di−hi−1][1,d_i-h_i-1] ，也就是说，最后需要将区间 [1,di−hi−1][1,d_i-h_i-1] 的和在 di−hid_i-h_i 减去，不然会影响到 ii 的父节点的合并。

这样就完成了系数 KK 的合并。

接下来就是还原 fi,jf_{i,j} 的值。这一点可以通过自上而下还原。因为 xx 一定永远是 ii 的祖先，在转移 ii 时， xx 必定被转移完了，所以无后效性。而且这里只需要维护和就行了，正好答案也求的是和，十分匹配。

具体来说就是遍历每个节点的线段树，同时累加前缀和。每到一个叶子节点，用前缀和加上叶子权值得到的结果与对应 sumxsum_x 相乘后返回。每到一个空节点，用前缀和乘上 sumsum 的对应区间和就行。因为我们不关心具体值，只在意和。

然后就完成了。于是你自认为 AC 了此题。

分析一下复杂度：线段树合并是 O(nlog⁡n)O(n\log n) 的，遍历是 O(n2)O(n^2) 的（不要像我一样想当然的认为是 O(nlog⁡n)O(n\log n) 的），常数比普通的大许多，但是实际前 55 个点表现优秀。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
const int N=100010,P=998244353,M=10000010;
int cid,T,n,d[N],sum[N],l[N],r[N],h[N],s[N],top;
int ls[M],rs[M],num[M],rt[N],idx;
vector<int>v[N];
void insert(int &p,int l,int r,int x,int y){
    if(!p)p=++idx;
    if(l==r){
        (num[p]+=y)%=P;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=x)insert(ls[p],l,mid,x,y);
    else insert(rs[p],mid+1,r,x,y);
    num[p]=(num[ls[p]]+num[rs[p]])%P;
}
void merge(int &x,int p,int q,int l,int r){
    if(!p||!q)return (void)(x=p+q);
    x=++idx;
    if(l==r){
        num[x]=(num[p]+num[q])%P;
        return ;
    }
    int mid=(l+r)>>1;
    merge(ls[x],ls[p],ls[q],l,mid);
    merge(rs[x],rs[p],rs[q],mid+1,r);
    num[x]=(num[ls[x]]+num[rs[x]])%P;
}
void Merge(int &p,int q,int l,int r,int ql,int qr){
    if(!q)return ;
    if(!p)p=++idx;
    if(ql<=l&&r<=qr){
        merge(p,p,q,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=ql)Merge(ls[p],ls[q],l,mid,ql,qr);
    if(mid<qr)Merge(rs[p],rs[q],mid+1,r,ql,qr);
    num[p]=(num[ls[p]]+num[rs[p]])%P;
}
int query(int p,int l,int r,int ql,int qr){
    if(!p)return 0;
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1,res=0;
    if(mid>=ql)(res+=query(ls[p],l,mid,ql,qr))%=P;
    if(mid<qr)(res+=query(rs[p],mid+1,r,ql,qr))%=P;
    return res;
}
void dfs(int x,int fa){
    d[x]=d[fa]+1;
    int L=d[x]-r[x],R=min(d[x]-h[x]-1,d[x]-l[x]);
    if(L<=R){
        insert(rt[x],1,n,L,1);
        if(R+1<=d[x]-h[x]-1)insert(rt[x],1,n,R+1,P-1);
    }
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        if(x!=1)Merge(rt[x],rt[u],1,n,1,d[x]-h[x]-1);
    }
    if(x!=1)insert(rt[x],1,n,d[x]-h[x],(P-query(rt[x],1,n,1,d[x]-h[x]-1))%P);
}
int relax(int p,int l,int r,int mx){
    if(!p)return 1ll*(s[r]-s[l-1]+P)%P*mx%P;
    if(l==r)return 1ll*(mx+num[p])%P*(s[l]-s[l-1]+P)%P;
    int mid=(l+r)>>1,res=0;
    int t=(mx+num[ls[p]])%P;
    return (relax(ls[p],l,mid,mx)+relax(rs[p],mid+1,r,t))%P;
}
int Relax(int &p,int l,int r,int ql,int qr,int mx){
    if(!p)p=++idx;
    if(ql<=l&&r<=qr)return relax(p,l,r,mx);
    int mid=(l+r)>>1,res=0;
    int t=(mx+num[ls[p]])%P;
    if(mid>=ql)(res+=Relax(ls[p],l,mid,ql,qr,mx))%=P;
    if(mid<qr)(res+=Relax(rs[p],mid+1,r,ql,qr,t))%=P;
    return res;
}
void dfs2(int x,int fa){
    if(x!=1){
        sum[x]=Relax(rt[x],1,n,1,d[x]-h[x]-1,0);
    }
    ++top;
    s[top]=(sum[x]+s[top-1])%P;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x);
    }
    top--;
}
int main(){
    scanf("%d%d",&cid,&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)v[i].clear(),sum[i]=0;
        for(int i=0;i<=idx;i++)num[i]=ls[i]=rs[i]=0;
        for(int i=0;i<=n;i++)rt[i]=0;
        idx=0;
        for(int i=2,x;i<=n;i++){
            scanf("%d%d%d%d",&x,l+i,r+i,h+i);
            v[x].push_back(i);
            v[i].push_back(x);
        }
        sum[1]=1;
        dfs(1,0);
        dfs2(1,0);
        for(int i=2;i<=n;i++)printf("%d ",sum[i]);puts("");
    }
    return 0;
}

100pts100pts ：优化线段树合并优化树形 DP

其实做出上一步已经很难了（我是怎么在半小时内想出上面的部分的？），如果上面的做出来了，这一步也不难。

容易发现复杂度瓶颈在 relax 函数的遍历。但是理论上线段树合并的遍历和这个遍历，或许是差不多的。

但是实际上一个 O(n2)O(n^2) 一个 O(nlog⁡n)O(n\log n) 。

Recall\text{Recall} 线段树合并的过程，为什么这个复杂度是 O(nlog⁡n)O(n\log n) ？原因是线段树合并过程中出现了节点公用，即一个节点同时存在于多棵动态开点线段树，由 if(!p||!q)return p+q; 这里看出。

那么这个也意味着，如果 relax 函数中，一个节点每次被访问的贡献一样，那么我就可以记录下他的贡献，下次遇到是直接返回，这样复杂度就也是 O(nlog⁡n)O(n\log n) 了。

至于每次进来时的贡献，容易发现这个节点本身的贡献是平凡的，这里指这个线段子树内的贡献，不包含这个数以前的前缀和贡献（即 mx ）。这是因为这个点线段子树内的权值一样，而会共用节点的线段树必然在树上构成祖孙关系，也就是说，属于同一个位置的数的那个 s[l]-s[l-1] 是一样的。

然后就是那个前缀和 mx 的贡献了。容易发现这个 mx 的贡献永远是 mx 所代表和的右侧的数的对应的 s[l]-s[l-1] 的贡献，使用乘法分配律得到 mx 贡献为 mx*(s[r]-s[l-1]) ，因此这一部分也是平凡的。

于是我们就解决了这道 NOI2024 的黑题（ D2T2 ），还是挺不错的一道题目。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;
const int N=100010,P=998244353,M=10000010;
int cid,T,n,d[N],sum[N],l[N],r[N],h[N],s[N],top;
int ls[M],rs[M],num[M],rt[N],idx,NUM[M];
vector<int>v[N];
void insert(int &p,int l,int r,int x,int y){
    if(!p)p=++idx;
    if(l==r){
        (num[p]+=y)%=P;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=x)insert(ls[p],l,mid,x,y);
    else insert(rs[p],mid+1,r,x,y);
    num[p]=(num[ls[p]]+num[rs[p]])%P;
}
void merge(int &x,int p,int q,int l,int r){
    if(!p||!q)return (void)(x=p+q);
    x=++idx;
    if(l==r){
        num[x]=(num[p]+num[q])%P;
        return ;
    }
    int mid=(l+r)>>1;
    merge(ls[x],ls[p],ls[q],l,mid);
    merge(rs[x],rs[p],rs[q],mid+1,r);
    num[x]=(num[ls[x]]+num[rs[x]])%P;
}
void Merge(int &p,int q,int l,int r,int ql,int qr){
    if(!q)return ;
    if(!p)p=++idx;
    if(ql<=l&&r<=qr){
        merge(p,p,q,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=ql)Merge(ls[p],ls[q],l,mid,ql,qr);
    if(mid<qr)Merge(rs[p],rs[q],mid+1,r,ql,qr);
    num[p]=(num[ls[p]]+num[rs[p]])%P;
}
int query(int p,int l,int r,int ql,int qr){
    if(!p)return 0;
    if(ql<=l&&r<=qr)return num[p];
    int mid=(l+r)>>1,res=0;
    if(mid>=ql)(res+=query(ls[p],l,mid,ql,qr))%=P;
    if(mid<qr)(res+=query(rs[p],mid+1,r,ql,qr))%=P;
    return res;
}
void dfs(int x,int fa){
    d[x]=d[fa]+1;
    int L=d[x]-r[x],R=min(d[x]-h[x]-1,d[x]-l[x]);
    if(L<=R){
        insert(rt[x],1,n,L,1);
        if(R+1<=d[x]-h[x]-1)insert(rt[x],1,n,R+1,P-1);
    }
    for(int u:v[x]){
        if(u==fa)continue;
        dfs(u,x);
        if(x!=1)Merge(rt[x],rt[u],1,n,1,d[x]-h[x]-1);
    }
    if(x!=1)insert(rt[x],1,n,d[x]-h[x],(P-query(rt[x],1,n,1,d[x]-h[x]-1))%P);
}
int relax(int p,int l,int r){
    if(!p)return 0;
    if(NUM[p]!=-1)return NUM[p];
    if(l==r)return NUM[p]=1ll*num[p]%P*(s[l]-s[l-1]+P)%P;
    int mid=(l+r)>>1,res=1ll*num[ls[p]]*(s[r]-s[mid]+P)%P;
    (res+=relax(ls[p],l,mid))%=P;
    (res+=relax(rs[p],mid+1,r))%=P;
    return NUM[p]=res;
}
int Relax(int &p,int l,int r,int ql,int qr,int mx){
    if(!p)p=++idx;
    if(ql<=l&&r<=qr)return (1ll*mx*(s[r]-s[l-1]+P)%P+relax(p,l,r))%P;
    int mid=(l+r)>>1,res=0;
    int t=(mx+num[ls[p]])%P;
    if(mid>=ql)(res+=Relax(ls[p],l,mid,ql,qr,mx))%=P;
    if(mid<qr)(res+=Relax(rs[p],mid+1,r,ql,qr,t))%=P;
    return res;
}
void dfs2(int x,int fa){
    if(x!=1){
        sum[x]=Relax(rt[x],1,n,1,d[x]-h[x]-1,0);
    }
    ++top;
    s[top]=(sum[x]+s[top-1])%P;
    for(int u:v[x]){
        if(u==fa)continue;
        dfs2(u,x);
    }
    top--;
}
int main(){
    scanf("%d%d",&cid,&T);
    memset(NUM,-1,sizeof(NUM));
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)v[i].clear(),sum[i]=0;
        for(int i=0;i<=idx;i++)num[i]=ls[i]=rs[i]=0,NUM[i]=-1;
        for(int i=0;i<=n;i++)rt[i]=0;
        idx=0;
        for(int i=2,x;i<=n;i++){
            scanf("%d%d%d%d",&x,l+i,r+i,h+i);
            v[x].push_back(i);
            v[i].push_back(x);
        }
        sum[1]=1;
        dfs(1,0);
        dfs2(1,0);
        for(int i=2;i<=n;i++)printf("%d ",sum[i]);puts("");
    }
    return 0;
}