Thoughts:
We can do this for each\(i\) Find the furthest point it can jump to and the closest point, and multiply the number of times to ask for it\(k\) A level ancestor is sufficient to make the\([l_i,r_i]\) newly expressed\(i\) Can jump to the depth in its ancestry in\([l_i,r_i]\) the point inside; and at the same time let\(lim_i = d_i - h_i-1\) indicate\(i\) At least jump to\(lim_i\) The depth of the
Consider the dynamic programming algorithm such that\(dp_i\) denote\(i\) The number of legal climbing sequences that depart to the summit.
Then it is equivalent to starting with\(i\) slip\(j\)and then from\(j\) jump to\(k\)Plus\(dp_k\) of the number of programs.
Then the state transfer equation is:
included among these\(W(i,j)\) indicate\(i \to j\) pathway\(lim_k\) minimum value of，Because the depth reached by each sprint must be less than the depth of all the points passed through the \(lim_k\)。
The plain realization is\(O(N^3)\) that consider optimization; noting that\(k\) be\(i\) of a section of depth-continuous points in the ancestor, then we can do a depth\(dp_i\) of the prefix sum, the difference is sufficient and the time complexity is optimized to\(O(N^2)\)The first time you do this, you'll get 25pts.
$O(N^2)$ Code：
namespace Sub1{
ll L,R,x,a,b;
ll s[N],dp[N],dep[N];
void dfs1(ll u){
for(auto v:E[u]){
if(v==fa[u])
continue;
dep[v]=dep[u]+1;
dfs1(v);
}
}
ll get(ll l,ll r){
if(!l)
return s[r];
return (s[r]-s[l-1]+mod)%mod;
}
void dfs3(ll u,ll Min,ll from){
L=l[u],R=min(r[u],Min);
if(L<=R)
dp[from]=(dp[from]+get(L,R))%mod;
for(auto v:E[u]){
if(v==fa[u])
continue;
dfs3(v,min(Min,h[v]),from);
}
}
void dfs2(ll u){
if(dep[u])
s[dep[u]]=(s[dep[u]-1]+dp[u])%mod;
else
s[dep[u]]=dp[u];
for(auto v:E[u]){
if(v==fa[u])
continue;
dfs3(v,h[v],v);
dfs2(v);
}
}
void solve(){
Read();
dfs1(1);
dp[1]=1;
For(i,2,n){
dp[i]=0;
x=i;
h[i]=dep[i]-h[i]-1;
while(r[i]){
x=fa[x];
l[i]--,r[i]--;
if(!l[i])
b=x;
if(!r[i])
a=x;
}
l[i]=dep[a],r[i]=dep[b];
}
dfs2(1);
For(i,2,n){
write(dp[i]);
putchar(' ');
}
putchar('\n');
}
void work(){
while(T--)
solve();
}
};
found\(u^k\) indicate\(u\) (used form a nominal expression)\(k\) Class Ancestor.
Consider it now.\(l_j=r_j\) The particular nature of the program, noting that for\(i\) Points within a subtree\(j\)At most, it will have no effect on the\(dp_i\) bring about\(dp_{j^{l_j}}\) contributions, noting that when\(W(i,j) < r_j\) time is not contributing.
Then we consider the enumeration\(j\)and noting that with the\(i\) The depth of the depth of the\(W(i,j)\) will also be smaller, consider solving for\(g_j\) denotes the depth of the smallest such that\(W(g_j,j) \ge r_j\) points, it is straightforward to multiply the solution.
In that case, for\(j \to g_j\) pathway\(i\) The point is that it is possible for the\(i\) slide down to\(j\) back sprint\(j^{l_j}\) of, then for the\(j \to g_j\) pathway\(dp_i\) are increased by the value of\(dp_{j^{l_j}}\)。
on the basis of\(j^{l_j}\) The depths of the process can be handled in order from smallest to largest.
Need to maintain path plus, single point lookup, can be direct tree dissection with tree arrays or line trees, time complexity is\(O(N \log^2 N)\)That gives us 45pts.
$O(N \log^2 N)$ Code：
class Tree{
public:
ll cnt=0;
ll p[N],t[N],z[N],d[N],fa[N];
struct Node{
ll l,r;
ll data;
ll tag;
}X[N<<2];
void dfs1(ll u,ll 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;
}
}
void dfs2(ll u,ll 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);
}
}
void build(ll k,ll l,ll r){
X[k].l=l,X[k].r=r;
X[k].data=X[k].tag=0;
if(l==r)
return ;
ll mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void add(ll k,ll v){
X[k].data=Add(X[k].data,v);
X[k].tag=Add(X[k].tag,v);
}
void push_down(ll k){
if(X[k].tag){
add(k<<1,X[k].tag);
add(k<<1|1,X[k].tag);
X[k].tag=0;
}
}
void update(ll k,ll l,ll r,ll v){
if(X[k].l==l&&r==X[k].r){
add(k,v);
return ;
}
push_down(k);
ll 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);
}
}
ll query(ll k,ll 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);
}
void update(ll u,ll v,ll 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);
}
void init(){
For(i,1,n)
z[i]=0;
cnt=0;
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
}
}Tr;
namespace Sub2{
ll x,cnt;
ll g[N],dep[N],Fa[N][M],F[N][M];
vector<pi> G[N];
void dfs1(ll 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;
dep[v]=dep[u]+1;
Fa[v][0]=u;
dfs1(v);
}
}
ll get_fa(ll u,ll k){
if(!k)
return u;
_For(j,0,M-1){
if(k>=(1ll<<j)){
k-=(1ll<<j);
u=Fa[u][j];
}
}
return u;
}
void dfs2(ll u){
For(j,1,M-1)
F[u][j]=min(F[u][j-1],F[Fa[u][j-1]][j-1]);
for(auto v:E[u]){
if(v==fa[u])
continue;
F[v][0]=h[v];
dfs2(v);
}
}
void solve(){
cnt=0;
Read();
();
For(j,0,M-1)
Fa[1][j]=1;
dfs1(1);
For(i,0,n-1)
G[i].clear();
For(i,2,n){
x=get_fa(i,l[i]);
l[i]=r[i]=dep[x];
h[i]=dep[i]-h[i]-1;
G[l[i]].push_back({i,x});
}
For(j,0,M-1)
F[1][j]=INF;
dfs2(1);
For(i,2,n){
x=i;
_For(j,0,M-1)
if(r[i]<=F[x][j])
x=Fa[x][j];
g[i]=dep[x]+1;
if(g[i]<=dep[i])
g[i]=get_fa(i,dep[i]-g[i]);
else
g[i]=-1;
}
(1,1,1);
For(i,0,n-1){
if(G[i].empty())
continue;
for(auto t:G[i]){
ll v=;
if(g[v]==-1)
continue;
(v,g[v],(1,dfn[]));
}
}
For(i,2,n){
write((1,dfn[i]));
putchar(' ');
}
putchar('\n');
}
void work(){
while(T--)
solve();
}
};
Consider now that according to the\(l_j=r_j\) The idea of finding\(l_j \ne r_j\) The situation.
Same thing. Enumeration.\(j\)Then, for a\(i\) will increase\(s_{\min(r_j,W(i,j))}-s_{l_j-1}\) contribution, of which\(s_u\) exist\(j\) on the chain of ancestors, denoting the depth of\(1 \sim u\) point-to-point\(dp\) Value.
Consider separate calculations and find that for\(-s_{l_j-1}\) The part that is\(l_j=r_j\) case, multiply to find the point with the smallest depth\(i\) feasible\(W(i,j) \ge l_j\)Then for\(i \to j\) The points on the path are increased\(-s_{l_j-1}\) The contribution of the
How it's being handled now\(s_{\min(r_j,W(i,j))}\) section, noting that it is definitely still better to take a section first\(r_j\)The same enumeration\(j\), multiply to find the depth-minimizing satisfaction\(W(i,j) > r_j\)(Note that the\(>\))\(i\)The following is a brief description of the\(j \to i\) pathway\(dp\) values, all of which have to be increased\(s_{r_j}\)。
Then consider dealing with\(s_{W(i,j)}\) case, consider the enumeration\(u\)makes\(lim_u\) be\(i \to j\) of the strict postfix minimum (i.e., the point with the deepest depth in the minimum), noting that we only need to ask for the\(u\) How many sub-trees are there within the\(j\) fulfillment\(u \to j\) There are no paths less than or equal to\(lim_u\) (used form a nominal expression)\(lim_k\)and\(lim_u \in [l_j,r_j]\)。
Only asked out for this\(j\) ordinal number\(sum\), then it can be multiplied to find the depth-minimizing\(i\) feasible\(W(i,u) = lim_u\)Then it's straightforward for\(i \to u\) The points on the path of the\(s_{lim_u} \times sum\) The contribution of the
Noting that there would be a sequencing problem with such an operation, consider solving for another\(s_x\) Only when it is time to consider\(l_j-1=x\) cap (a poem)\(r_j = x\) cap (a poem)\(lim_u=x\) The contribution of the
This part of the Violence Code:
namespace Sub3{
ll Min,sum,x,a,b,c,t;
ll dep[N],dp[N],g1[N],g2[N],g3[N];
ll Fa[N][M];
vector<pi> E1[N],E2[N],E3[N];
void dfs(ll 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);
}
}
ll get_fa(ll u,ll k){
if(!k)
return u;
_For(j,0,M-1){
if(k>=(1ll<<j)){
k-=(1ll<<j);
u=Fa[u][j];
}
}
return u;
}
ll get_sum(ll u){
ll ans=0;
while(u){
ans=Add(ans,dp[u]);
u=fa[u];
}
return ans;
}
void dfs2(ll u,ll k){
if(h[u]<=h[k]&&u!=k)
return ;
if(l[u]<=h[k]&&h[k]<=r[u])
sum++;
for(auto v:E[u]){
if(v==fa[u])
continue;
dfs2(v,k);
}
}
void solve(){
Read();
dfs(1);
dp[1]=1;
For(i,0,n-1){
E1[i].clear();
E2[i].clear();
E3[i].clear();
}
For(i,2,n){
dp[i]=0;
x=i;
t=h[i]+1;
h[i]=dep[i]-h[i]-1;
while(l[i]>=1||r[i]>=1||t>=1){
x=fa[x];
l[i]--,r[i]--,t--;
if(!l[i])
b=x;
if(!r[i])
a=x;
if(!t)
c=x;
}
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});
}
//cerr<<'\n';
For(i,2,n){
if(l[i]){
Min=INF;
x=i,a=-1;
while(fa[x]!=1){
Min=min(Min,h[x]);
if(Min<l[i])
break;
a=x;
x=fa[x];
}
g1[i]=a;
}
else
g1[i]=-1;
Min=INF;
x=i,a=-1;
while(fa[x]!=1){
Min=min(Min,h[x]);
if(Min<=r[i])
break;
a=x;
x=fa[x];
}
g2[i]=a;
x=i;
while(fa[x]!=1){
if(h[fa[x]]<h[i])
break;
x=fa[x];
}
g3[i]=x;
//cerr<<i<<':'<<g1[i]<<','<<g2[i]<<','<<g3[i]<<'\n';
}
//cerr<<'\n';
For(i,0,n-1){
for(auto t:E1[i]){
x=,a=get_sum(),b=g1[x];
if(b==-1)
continue;
//cerr<<"("<<x<<"->"<<b<<")-"<<a<<'\n';
while(x!=fa[b]){
dp[x]=(dp[x]-a+mod)%mod;
x=fa[x];
}
}
for(auto t:E2[i]){
x=,a=get_sum(),b=g2[x];
if(b==-1)
continue;
//cerr<<"("<<x<<"->"<<b<<")+"<<a<<'\n';
while(x!=fa[b]){
dp[x]=Add(dp[x],a);
x=fa[x];
}
}
for(auto t:E3[i]){
x=,a=get_sum(),b=g3[x];
if(b==-1)
continue;
sum=0;
dfs2(x,x);
//cerr<<"("<<x<<"->"<<b<<")+"<<sum<<'*'<<a<<'\n';
while(x!=fa[b]){
dp[x]=(dp[x]+sum*a%mod)%mod;
x=fa[x];
}
}
}
For(i,2,n){
write(dp[i]);
putchar(' ');
}
putchar('\n');
}
void work(){
while(T--)
solve();
}
};
In this case the operations are some basic operations, chain addition, chain checking, multiplication optimization, etc. The only thing you need to pay attention to is the query\(u\) How many sub-trees are there within the\(j\) fulfillment\(u \to j\) There are no paths less than or equal to\(lim_u\) (used form a nominal expression)\(lim_k\)and\(lim_u \in [l_j,r_j]\)。
Consideration for\(i\) locate\(i \to 1\) The first one on the path that satisfies the\(lim_j < lim_i\) (used form a nominal expression)\(j\)So what's the point?\(Fa_i = j\)。
According to this\(Fa\)The constructed edge is\(i \to Fa_i\) of the new tree, then the above query becomes a query to find the new tree in the\(u\) Points within a subtree\(j\) fulfillment\(lim_u \in [l_j,r_j]\) The proof is obvious and will not be elaborated.
Then it is possible to set the\([l_j,r_j]\) confined\(sum_i\) rise\(1\), then the number of numbers that satisfy the condition is\(sum_{lim_u}\)。
Consider the dfn sequence for a new tree, then\(u\) Points within a subtree can be counted as an interval\([L,R]\)and then build a prefixed chairmans tree to quickly find\(lim_u\) The number of intervals that are contained by the interval (since they are to be interval-added, they can be directly marked for permanence).
It can also be done with dsu on tree, but personallytoo goodIt won't.
The total time complexity is\(O(N \log^2 N)\)。
Note that the space for the President's tree is open\(50\) Times.
Full Code;
#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);
}
();
(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=,b=g1[x];
if(b==-1)
continue;
a=(1,);
(x,b,mod-a);
}
for(auto t:E2[i]){
x=,b=g2[x];
if(b==-1)
continue;
a=(1,);
(x,b,a);
}
for(auto t:E3[i]){
x=,b=g3[x];
if(b==-1)
continue;
a=(1,);
sum=Seg::Ask(x);
(x,b,1ll*sum*a%mod);
}
}
For(i,2,n){
write((1,dfn[i]));
putchar(' ');
}
putchar('\n');
}
inline void work(){
while(T--)
solve();
}
};
int main(){
//open("","");
read(),T=read();
Std::work();
return 0;
}