题解：P11824 [湖北省选模拟 2025] 团队协作 / team
当题解区全是线段树的时候，一篇树剖+线段树题解就是救赎！
Solution
Step 1
考虑转置原理，这里官方题解已经讲的很清楚了，所以适当省略。
这个题的矩阵
转置之后就是
转置之后的问题就是最大值为
这个问题可以 DDP 做，每个重链开线段树，每个节点轻儿子开线段树（不需要操作的逆），记录每次操作，发现可以只有
record
#include<bits/stdc++.h>
using namespace std;
bool bg_memory;
chrono::_V2::system_clock::time_point bg_clock,en_clock;
void debugTime(){
en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
double duration_count=duration_clock.count()*0.001;
cerr<<"Time:"<<duration_count<<"ms"<<endl;
}
namespace GENSOKYO{
template<typename T>
void read(T &a){
char c;a=0;int f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
do a=a*10+c-'0';
while(isdigit(c=getchar()));
a*=f;
}
template<typename T>
void write(T a){
if(a<0)putchar('-'),a=-a;
if(a>=10)write(a/10);
putchar('0'+a%10);
}
char GC(){
char c=getchar();
while(c<=32)c=getchar();
return c;
}
template<typename T1,typename T2>
void chmin(T1 &x,T2 y){if(x>y)x=y;}
template<typename T1,typename T2>
void chmax(T1 &x,T2 y){if(x<y)x=y;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
typedef __int128 lll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int RRand(int n){return (ull)rng()*n>>32;}
int RRand(int l,int r){return l+RRand(r-l+1);}
void gskinit(){
}
const int MAXN=300010;
const int P=998244353;
int n,fa[MAXN];
vector<int> G[MAXN];
int v[MAXN];
struct Op{
int *x,*y,v;//x+=y*v;
Op(){}
Op(int *x,int *y,int v):x(x),y(y),v(v){}
};
struct Pr{
int val,cnt;
Pr(){cnt=1;}
};
struct Mat{
Pr a[2][2];
Mat(){a[1][0].cnt=a[1][1].cnt=0;}
};
Op seq[20000010];int scnt;
void add(int *x,int *y,int v){
// scnt++;
seq[scnt++]=Op(x,y,v);
}
void assign(int &A,int &B,int v=1){
// scnt++;
seq[scnt++]=Op(&A,&B,v==0?-P:-v);
}
void assign(Pr &A,Pr &B){
assign(A.val,B.val);
A.cnt=B.cnt;
}
void assign(Mat &A,Mat &B){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
assign(A.a[i][j],B.a[i][j]);
}
void Add(Pr &A,Pr &B,Pr &C){
assign(A.val,B.val,1);
add(&A.val,&C.val,1);
A.cnt=(B.cnt+C.cnt)%P;
}
void Mult(Pr &A,Pr &B,Pr &C){
assign(A.val,B.val,C.cnt);
add(&A.val,&C.val,B.cnt);
A.cnt=(ll)B.cnt*C.cnt%P;
}
void Mult(Mat &A,Mat &B,Mat &C){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j){
assign(A.a[i][j].val,B.a[i][0].val,C.a[0][j].cnt);
add(&A.a[i][j].val,&C.a[0][j].val,B.a[i][0].cnt);
add(&A.a[i][j].val,&B.a[i][1].val,C.a[1][j].cnt);
add(&A.a[i][j].val,&C.a[1][j].val,B.a[i][1].cnt);
A.a[i][j].cnt=((ll)B.a[i][0].cnt*C.a[0][j].cnt+(ll)B.a[i][1].cnt*C.a[1][j].cnt)%P;
}
}
Pr ptmp1,ptmp2,ptmp3;
Mat mtmp1,mtmp2,mtmp3;
namespace SEGM{
int sgtot;
Mat t[MAXN<<2];
int ch[MAXN<<2][2];
#define mid (L+R>>1)
void build(int &x,int L,int R){
if(!x)x=++sgtot;
if(L==R){
}else{
build(ch[x][0],L,mid);
build(ch[x][1],mid+1,R);
}
}
void pushup(int x){
Mult(t[x],t[ch[x][0]],t[ch[x][1]]);
}
void upd(int &x,int pos,Mat &v,int L,int R){
if(L==R){
assign(t[x],v);
}else{
if(pos<=mid)upd(ch[x][0],pos,v,L,mid);
else upd(ch[x][1],pos,v,mid+1,R);
pushup(x);
}
}
#undef mid
}
namespace SEGP{
Pr a[MAXN<<2],b[MAXN<<2];int sgtot;
int ch[MAXN<<2][2];
// a: 0+1 ; b: 0
#define mid (L+R>>1)
void build(int &x,int L,int R){
if(!x)x=++sgtot;
if(L==R){
}else{
build(ch[x][0],L,mid);
build(ch[x][1],mid+1,R);
}
}
void pushup(int x){
Mult(a[x],a[ch[x][0]],a[ch[x][1]]);
Mult(b[x],b[ch[x][0]],b[ch[x][1]]);
}
void upd(int &x,int pos,Pr &A,Pr &B,int L,int R){
if(L==R){
assign(a[x],A);
assign(b[x],B);
}else{
if(pos<=mid)upd(ch[x][0],pos,A,B,L,mid);
else upd(ch[x][1],pos,A,B,mid+1,R);
pushup(x);
}
}
#undef mid
}
int siz[MAXN],hson[MAXN],top[MAXN],dfn[MAXN],fdfn[MAXN],bot[MAXN],dfc;
int lid[MAXN];//light son id
int hrt[MAXN],lrt[MAXN];// heavy chain segT ; light son segT
void dfs1(int x){
siz[x]=1;hson[x]=0;
for(int y:G[x]){
dfs1(y);
if(siz[y]>siz[hson[x]])hson[x]=y;
siz[x]+=siz[y];
}
}
void dfs2(int x,int topf){
fdfn[dfn[x]=++dfc]=x;
top[x]=topf;
bot[top[x]]=x;
if(hson[x])dfs2(hson[x],topf);
for(int y:G[x])if(y!=hson[x]){
dfs2(y,y);
}
}
Pr c[MAXN];// the coefficient for vertex x
Mat d[MAXN];// the matrix for vertex x
int oans[MAXN];
void main(){
read(n);
for(int i=2;i<=n;++i){
read(fa[i]);
G[fa[i]].emplace_back(i);
}
for(int i=1;i<=n;++i)read(v[i]),c[i].cnt=0;
vector<int> ord(n);
for(int i=0;i<n;++i)ord[i]=i+1;
sort(ord.begin(),ord.end(),[&](int x,int y){return v[x]<v[y];});
dfs1(1),dfs2(1,1);
for(int i=1;i<=n;++i)if(top[i]==i)SEGM::build(hrt[i],1,dfn[bot[i]]-dfn[i]+1);
for(int x=1;x<=n;++x){
if(G[x].size()>1){
int cnt=0;
for(auto y:G[x])if(y!=hson[x])lid[y]=++cnt;
SEGP::build(lrt[x],1,cnt);
}
}
for(int i=1;i<=n;++i){
int x=ord[i-1];
add(&c[x].val,&v[x],1);
c[x].cnt=1;
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
int y;
while((y=top[x])!=1){
assign(ptmp1,SEGM::t[hrt[y]].a[0][0]);
assign(ptmp2,SEGM::t[hrt[y]].a[1][0]);
Add(ptmp3,ptmp1,ptmp2);
x=fa[y];
SEGP::upd(lrt[x],lid[y],ptmp3,ptmp1,1,G[x].size()-1);
assign(d[x].a[0][0],SEGP::a[lrt[x]]);
assign(d[x].a[0][1],SEGP::a[lrt[x]]);
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
}
x=ord[i-1];
add(&oans[x],&SEGM::t[hrt[1]].a[0][0].val,1);
add(&oans[x],&SEGM::t[hrt[1]].a[1][0].val,1);
}
for(int i=n;i>=2;--i)add(&oans[ord[i-1]],&oans[ord[i-2]],P-1);
for(int i=1;i<=n;++i)assign(v[i],oans[i]);
reverse(seq,seq+scnt);
cerr<<scnt<<endl;
for(int i=0;i<scnt;++i){
Op x=seq[i];
if(x.v<0)*x.y=(*x.y+(ll)*x.x*(-x.v))%P,*x.x=0;
else *x.y=(*x.y+(ll)*x.x*x.v)%P;
}
for(int i=1;i<=n;++i)printf("%d ",v[i]);puts("");
}
}
bool en_memory;
signed main(){
bg_clock=chrono::high_resolution_clock::now();
GENSOKYO::gskinit();
int T=1;//cin>>T;
while(T--)GENSOKYO::main();
debugTime();
double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
cerr<<"Memory: "<<memory_used<<"MB"<<endl;
return 0;
}Step 2
操作序列是
考虑全局平衡二叉树，但是一个点的轻儿子平衡树不行。笔者不会 Top tree 但是似乎 toptree 可以通过 Rake 操作平衡做到这一点。
怎么办？观察这个操作，转置的话，其实不需要全记，倒着修改每一个点，每一段记录然后分别转置就好了。
但是这样的话就要记录每一个版本了怎么办？可以每次手动回退版本。这也是容易的具体可以看看代码。
record
#include<bits/stdc++.h>
using namespace std;
bool bg_memory;
chrono::_V2::system_clock::time_point bg_clock,en_clock;
void debugTime(){
en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
double duration_count=duration_clock.count()*0.001;
cerr<<"Time:"<<duration_count<<"ms"<<endl;
}
namespace GENSOKYO{
template<typename T>
void read(T &a){
char c;a=0;int f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
do a=a*10+c-'0';
while(isdigit(c=getchar()));
a*=f;
}
template<typename T>
void write(T a){
if(a<0)putchar('-'),a=-a;
if(a>=10)write(a/10);
putchar('0'+a%10);
}
char GC(){
char c=getchar();
while(c<=32)c=getchar();
return c;
}
template<typename T1,typename T2>
void chmin(T1 &x,T2 y){if(x>y)x=y;}
template<typename T1,typename T2>
void chmax(T1 &x,T2 y){if(x<y)x=y;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
typedef __int128 lll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int RRand(int n){return (ull)rng()*n>>32;}
int RRand(int l,int r){return l+RRand(r-l+1);}
void gskinit(){
}
const int MAXN=300010;
const int P=998244353;
int n,fa[MAXN];
vector<int> G[MAXN];
int v[MAXN];
struct Op{
int *x,*y,v;//x+=y*v;
bool type;
Op(){}
Op(int *_x,int *_y,int _v):x(_x),y(_y){type=_v<0;v=_v<0?-_v:_v;}
};
struct Pr{
int val,cnt;
Pr(){cnt=1;}
};
struct Mat{
Pr a[2][2];
Mat(){a[1][0].cnt=a[1][1].cnt=0;}
};
Op seq[1000010];int scnt;
bool record;
void add(int *x,int *y,int v){
if(!record)return;
seq[scnt++]=Op(x,y,v);
}
void assign(int &A,int &B,int v=1){
if(!record)return;
seq[scnt++]=Op(&A,&B,v==0?-P:-v);
assert(seq[scnt-1].v>=0);
}
void assign(Pr &A,Pr &B){
A.cnt=B.cnt;
assign(A.val,B.val);
}
void assign(Mat &A,Mat &B){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
assign(A.a[i][j],B.a[i][j]);
}
void Add(Pr &A,Pr &B,Pr &C){
assign(A.val,B.val,1);
add(&A.val,&C.val,1);
A.cnt=(B.cnt+C.cnt)%P;
}
void Mult(Pr &A,Pr &B,Pr &C){
assign(A.val,B.val,C.cnt);
add(&A.val,&C.val,B.cnt);
A.cnt=(ll)B.cnt*C.cnt%P;
}
void Mult(Mat &A,Mat &B,Mat &C){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j){
assign(A.a[i][j].val,B.a[i][0].val,C.a[0][j].cnt);
add(&A.a[i][j].val,&C.a[0][j].val,B.a[i][0].cnt);
add(&A.a[i][j].val,&B.a[i][1].val,C.a[1][j].cnt);
add(&A.a[i][j].val,&C.a[1][j].val,B.a[i][1].cnt);
A.a[i][j].cnt=((ll)B.a[i][0].cnt*C.a[0][j].cnt+(ll)B.a[i][1].cnt*C.a[1][j].cnt)%P;
}
}
Pr ptmp1,ptmp2,ptmp3;
namespace SEGM{
int sgtot;
Mat t[MAXN<<2];
int ch[MAXN<<2][2];
#define mid (L+R>>1)
void build(int &x,int L,int R){
if(!x)x=++sgtot;
if(L==R){
}else{
build(ch[x][0],L,mid);
build(ch[x][1],mid+1,R);
}
}
void pushup(int x){
Mult(t[x],t[ch[x][0]],t[ch[x][1]]);
}
void upd(int x,int pos,Mat &v,int L,int R){
if(L==R){
assign(t[x],v);
}else{
if(pos<=mid)upd(ch[x][0],pos,v,L,mid);
else upd(ch[x][1],pos,v,mid+1,R);
pushup(x);
}
}
#undef mid
}
namespace SEGP{
Pr a[MAXN<<2],b[MAXN<<2];int sgtot;
int ch[MAXN<<2][2];
// a: 0+1 ; b: 0
#define mid (L+R>>1)
void build(int &x,int L,int R){
if(!x)x=++sgtot;
if(L==R){
}else{
build(ch[x][0],L,mid);
build(ch[x][1],mid+1,R);
}
}
void pushup(int x){
Mult(a[x],a[ch[x][0]],a[ch[x][1]]);
Mult(b[x],b[ch[x][0]],b[ch[x][1]]);
}
void upd(int x,int pos,Pr &A,Pr &B,int L,int R){
if(L==R){
assign(a[x],A);
assign(b[x],B);
}else{
if(pos<=mid)upd(ch[x][0],pos,A,B,L,mid);
else upd(ch[x][1],pos,A,B,mid+1,R);
pushup(x);
}
}
#undef mid
}
int siz[MAXN],hson[MAXN],top[MAXN],dfn[MAXN],fdfn[MAXN],bot[MAXN],dfc;
int lid[MAXN];//light son id
int hrt[MAXN],lrt[MAXN];// heavy chain segT ; light son segT
void dfs1(int x){
siz[x]=1;hson[x]=0;
for(int y:G[x]){
dfs1(y);
if(siz[y]>siz[hson[x]])hson[x]=y;
siz[x]+=siz[y];
}
}
void dfs2(int x,int topf){
fdfn[dfn[x]=++dfc]=x;
top[x]=topf;
bot[top[x]]=x;
if(hson[x])dfs2(hson[x],topf);
for(int y:G[x])if(y!=hson[x]){
dfs2(y,y);
}
}
Pr c[MAXN];// the coefficient for vertex x
Mat d[MAXN];// the matrix for vertex x
int oans[MAXN];
void execute(){
for(int i=scnt-1;~i;--i){
*seq[i].y=(*seq[i].y+(ll)*seq[i].x*seq[i].v)%P;
if(seq[i].type)*seq[i].x=0;
}
}
int _0;
void main(){
read(n);
for(int i=2;i<=n;++i){
read(fa[i]);
G[fa[i]].emplace_back(i);
}
for(int i=1;i<=n;++i)read(v[i]),c[i].cnt=0;
vector<int> ord(n);
for(int i=0;i<n;++i)ord[i]=i+1;
sort(ord.begin(),ord.end(),[&](int x,int y){return v[x]<v[y];});
dfs1(1),dfs2(1,1);
for(int i=1;i<=n;++i)if(top[i]==i)SEGM::build(hrt[i],1,dfn[bot[i]]-dfn[i]+1);
for(int x=1;x<=n;++x){
if(G[x].size()>1){
int cnt=0;
for(auto y:G[x])if(y!=hson[x])lid[y]=++cnt;
SEGP::build(lrt[x],1,cnt);
}
}
record=0;
for(int i=1;i<=n;++i){
int x=ord[i-1];
add(&c[x].val,&v[x],1);
c[x].cnt=1;
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
int y;
while((y=top[x])!=1){
assign(ptmp1,SEGM::t[hrt[y]].a[0][0]);
assign(ptmp2,SEGM::t[hrt[y]].a[1][0]);
Add(ptmp3,ptmp1,ptmp2);
x=fa[y];
SEGP::upd(lrt[x],lid[y],ptmp3,ptmp1,1,G[x].size()-1);
assign(d[x].a[0][0],SEGP::a[lrt[x]]);
assign(d[x].a[0][1],SEGP::a[lrt[x]]);
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
}
x=ord[i-1];
add(&oans[x],&SEGM::t[hrt[1]].a[0][0].val,1);
add(&oans[x],&SEGM::t[hrt[1]].a[1][0].val,1);
}
record=1;
scnt=0;
for(int i=n;i>=2;--i)add(&oans[ord[i-1]],&oans[ord[i-2]],P-1);
for(int i=1;i<=n;++i)assign(v[i],oans[i]);
execute();
scnt=0;
for(int i=n,x;i>=1;--i){
auto process=[&](int val){
x=ord[i-1];
add(&c[x].val,&v[x],1);
c[x].cnt=val;
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
int y;
while((y=top[x])!=1){
assign(ptmp1,SEGM::t[hrt[y]].a[0][0]);
assign(ptmp2,SEGM::t[hrt[y]].a[1][0]);
Add(ptmp3,ptmp1,ptmp2);
x=fa[y];
SEGP::upd(lrt[x],lid[y],ptmp3,ptmp1,1,G[x].size()-1);
assign(d[x].a[0][0],SEGP::a[lrt[x]]);
assign(d[x].a[0][1],SEGP::a[lrt[x]]);
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
}
x=ord[i-1];
add(&oans[x],&SEGM::t[hrt[1]].a[0][0].val,1);
add(&oans[x],&SEGM::t[hrt[1]].a[1][0].val,1);
};
record=0;
process(0);
record=1;
process(1);
execute();
record=0,scnt=0;
process(0);
}
for(int i=1;i<=n;++i)printf("%d ",v[i]);puts("");
}
}
bool en_memory;
signed main(){
bg_clock=chrono::high_resolution_clock::now();
GENSOKYO::gskinit();
int T=1;//cin>>T;
while(T--)GENSOKYO::main();
debugTime();
double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
cerr<<"Memory: "<<memory_used<<"MB"<<endl;
return 0;
}Step 3
卡常！
首先删除线段树中动态开点的 &x 引用。
然后开 inline
展开矩阵乘法。
使用 c++23。
然后就可以通过！
record
#include<bits/stdc++.h>
using namespace std;
bool bg_memory;
chrono::_V2::system_clock::time_point bg_clock,en_clock;
void debugTime(){
en_clock=chrono::high_resolution_clock::now();
auto duration_clock=chrono::duration_cast<chrono::microseconds>(en_clock-bg_clock);
double duration_count=duration_clock.count()*0.001;
cerr<<"Time:"<<duration_count<<"ms"<<endl;
}
namespace GENSOKYO{
template<typename T>
void read(T &a){
char c;a=0;int f=1;
while(!isdigit(c=getchar()))if(c=='-')f=-1;
do a=a*10+c-'0';
while(isdigit(c=getchar()));
a*=f;
}
template<typename T>
void write(T a){
if(a<0)putchar('-'),a=-a;
if(a>=10)write(a/10);
putchar('0'+a%10);
}
char GC(){
char c=getchar();
while(c<=32)c=getchar();
return c;
}
template<typename T1,typename T2>
void chmin(T1 &x,T2 y){if(x>y)x=y;}
template<typename T1,typename T2>
void chmax(T1 &x,T2 y){if(x<y)x=y;}
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int,int> PII;
typedef pair<ll,int> PLI;
typedef __int128 lll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int RRand(int n){return (ull)rng()*n>>32;}
int RRand(int l,int r){return l+RRand(r-l+1);}
void gskinit(){
}
const int MAXN=300010;
const int P=998244353;
int n,fa[MAXN];
vector<int> G[MAXN];
int v[MAXN];
struct Op{
int *x,*y,v;//x+=y*v;
bool type;
Op(){}
Op(int *_x,int *_y,int _v):x(_x),y(_y){type=_v<0;v=_v<0?-_v:_v;}
};
struct Pr{
int val,cnt;
Pr(){cnt=1;}
};
struct Mat{
Pr a[2][2];
Mat(){a[1][0].cnt=a[1][1].cnt=0;}
};
Op seq[2010];int scnt;
bool record;
inline void add(int *x,int *y,int v){
if(!record)return;
seq[scnt++]=Op(x,y,v);
}
inline void assign(int &A,int &B,int v=1){
if(!record)return;
seq[scnt++]=Op(&A,&B,v==0?-P:-v);
assert(seq[scnt-1].v>=0);
}
inline void assign(Pr &A,Pr &B){
A.cnt=B.cnt;
if(!record)return;
assign(A.val,B.val);
}
inline void assign(Mat &A,Mat &B){
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
assign(A.a[i][j],B.a[i][j]);
}
inline void Add(Pr &A,Pr &B,Pr &C){
A.cnt=(B.cnt+C.cnt)%P;
if(!record)return;
assign(A.val,B.val,1);
add(&A.val,&C.val,1);
}
inline void Mult(Pr &A,Pr &B,Pr &C){
A.cnt=(ll)B.cnt*C.cnt%P;
if(!record)return;
assign(A.val,B.val,C.cnt);
add(&A.val,&C.val,B.cnt);
}
inline void Mult(Mat &A,Mat &B,Mat &C){
A.a[0][0].cnt=((ll)B.a[0][0].cnt*C.a[0][0].cnt+(ll)B.a[0][1].cnt*C.a[1][0].cnt)%P;
A.a[0][1].cnt=((ll)B.a[0][0].cnt*C.a[0][1].cnt+(ll)B.a[0][1].cnt*C.a[1][1].cnt)%P;
A.a[1][0].cnt=((ll)B.a[1][0].cnt*C.a[0][0].cnt+(ll)B.a[1][1].cnt*C.a[1][0].cnt)%P;
A.a[1][1].cnt=((ll)B.a[1][0].cnt*C.a[0][1].cnt+(ll)B.a[1][1].cnt*C.a[1][1].cnt)%P;
if(!record)return;
#define MAT_MUL_2X2(Aij, Bi0, Bi1, C0j, C1j) \
{ \
assign((Aij).val, (Bi0).val, (C0j).cnt);\
add(&(Aij).val, &(C0j).val, (Bi0).cnt);\
add(&(Aij).val, &(Bi1).val, (C1j).cnt);\
add(&(Aij).val, &(C1j).val, (Bi1).cnt);\
}
MAT_MUL_2X2(A.a[0][0],B.a[0][0], B.a[0][1],C.a[0][0], C.a[1][0]);
MAT_MUL_2X2(A.a[0][1],B.a[0][0], B.a[0][1],C.a[0][1], C.a[1][1]);
MAT_MUL_2X2(A.a[1][0],B.a[1][0], B.a[1][1],C.a[0][0], C.a[1][0]);
MAT_MUL_2X2(A.a[1][1],B.a[1][0], B.a[1][1],C.a[0][1], C.a[1][1]);
}
Pr ptmp1,ptmp2,ptmp3;
namespace SEGM{
int sgtot;
Mat t[MAXN<<2];
int ch[MAXN<<2][2];
#define mid (L+R>>1)
void build(int &x,int L,int R){
if(!x)x=++sgtot;
if(L==R){
}else{
build(ch[x][0],L,mid);
build(ch[x][1],mid+1,R);
}
}
void pushup(int x){
Mult(t[x],t[ch[x][0]],t[ch[x][1]]);
}
void upd(int x,int pos,Mat &v,int L,int R){
if(L==R){
assign(t[x],v);
}else{
if(pos<=mid)upd(ch[x][0],pos,v,L,mid);
else upd(ch[x][1],pos,v,mid+1,R);
pushup(x);
}
}
#undef mid
}
namespace SEGP{
Pr a[MAXN<<2],b[MAXN<<2];int sgtot;
int ch[MAXN<<2][2];
// a: 0+1 ; b: 0
#define mid (L+R>>1)
void build(int &x,int L,int R){
if(!x)x=++sgtot;
if(L==R){
}else{
build(ch[x][0],L,mid);
build(ch[x][1],mid+1,R);
}
}
void pushup(int x){
Mult(a[x],a[ch[x][0]],a[ch[x][1]]);
Mult(b[x],b[ch[x][0]],b[ch[x][1]]);
}
void upd(int x,int pos,Pr &A,Pr &B,int L,int R){
if(L==R){
assign(a[x],A);
assign(b[x],B);
}else{
if(pos<=mid)upd(ch[x][0],pos,A,B,L,mid);
else upd(ch[x][1],pos,A,B,mid+1,R);
pushup(x);
}
}
#undef mid
}
int siz[MAXN],hson[MAXN],top[MAXN],dfn[MAXN],fdfn[MAXN],bot[MAXN],dfc;
int lid[MAXN];//light son id
int hrt[MAXN],lrt[MAXN];// heavy chain segT ; light son segT
void dfs1(int x){
siz[x]=1;hson[x]=0;
for(int y:G[x]){
dfs1(y);
if(siz[y]>siz[hson[x]])hson[x]=y;
siz[x]+=siz[y];
}
}
void dfs2(int x,int topf){
fdfn[dfn[x]=++dfc]=x;
top[x]=topf;
bot[top[x]]=x;
if(hson[x])dfs2(hson[x],topf);
for(int y:G[x])if(y!=hson[x]){
dfs2(y,y);
}
}
Pr c[MAXN];// the coefficient for vertex x
Mat d[MAXN];// the matrix for vertex x
int oans[MAXN];
void execute(){
for(int i=scnt-1;~i;--i){
*seq[i].y=(*seq[i].y+(ll)*seq[i].x*seq[i].v)%P;
if(seq[i].type)*seq[i].x=0;
}
}
int _0;
void main(){
read(n);
for(int i=2;i<=n;++i){
read(fa[i]);
G[fa[i]].emplace_back(i);
}
for(int i=1;i<=n;++i)read(v[i]),c[i].cnt=0;
vector<int> ord(n);
for(int i=0;i<n;++i)ord[i]=i+1;
sort(ord.begin(),ord.end(),[&](int x,int y){return v[x]<v[y];});
dfs1(1),dfs2(1,1);
for(int i=1;i<=n;++i)if(top[i]==i)SEGM::build(hrt[i],1,dfn[bot[i]]-dfn[i]+1);
for(int x=1;x<=n;++x){
if(G[x].size()>1){
int cnt=0;
for(auto y:G[x])if(y!=hson[x])lid[y]=++cnt;
SEGP::build(lrt[x],1,cnt);
}
}
record=0;
for(int i=1;i<=n;++i){
int x=ord[i-1];
add(&c[x].val,&v[x],1);
c[x].cnt=1;
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
int y;
while((y=top[x])!=1){
assign(ptmp1,SEGM::t[hrt[y]].a[0][0]);
assign(ptmp2,SEGM::t[hrt[y]].a[1][0]);
Add(ptmp3,ptmp1,ptmp2);
x=fa[y];
SEGP::upd(lrt[x],lid[y],ptmp3,ptmp1,1,G[x].size()-1);
assign(d[x].a[0][0],SEGP::a[lrt[x]]);
assign(d[x].a[0][1],SEGP::a[lrt[x]]);
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
}
x=ord[i-1];
add(&oans[x],&SEGM::t[hrt[1]].a[0][0].val,1);
add(&oans[x],&SEGM::t[hrt[1]].a[1][0].val,1);
}
for(int i=1;i<=n;++i)oans[i]=v[i],v[i]=0;
for(int i=1;i<=n-1;++i)oans[ord[i-1]]=(oans[ord[i-1]]+(ll)oans[ord[i]]*(P-1))%P;
for(int i=n,x;i>=1;--i){
auto process=[&](int val){
x=ord[i-1];
add(&c[x].val,&v[x],1);
c[x].cnt=val;
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
int y;
while((y=top[x])!=1){
assign(ptmp1,SEGM::t[hrt[y]].a[0][0]);
assign(ptmp2,SEGM::t[hrt[y]].a[1][0]);
Add(ptmp3,ptmp1,ptmp2);
x=fa[y];
SEGP::upd(lrt[x],lid[y],ptmp3,ptmp1,1,G[x].size()-1);
assign(d[x].a[0][0],SEGP::a[lrt[x]]);
assign(d[x].a[0][1],SEGP::a[lrt[x]]);
Mult(d[x].a[1][0],c[x],SEGP::b[lrt[x]]);
SEGM::upd(hrt[top[x]],dfn[x]-dfn[top[x]]+1,d[x],1,dfn[bot[top[x]]]-dfn[top[x]]+1);
}
x=ord[i-1];
add(&oans[x],&SEGM::t[hrt[1]].a[0][0].val,1);
add(&oans[x],&SEGM::t[hrt[1]].a[1][0].val,1);
};
record=0;
process(0);
scnt=0;record=1;
process(1);
execute();
record=0;
process(0);
}
for(int i=1;i<=n;++i)write(v[i]),putchar(' ');puts("");
}
}
bool en_memory;
signed main(){
bg_clock=chrono::high_resolution_clock::now();
GENSOKYO::gskinit();
int T=1;//cin>>T;
while(T--)GENSOKYO::main();
debugTime();
double memory_used=(&en_memory-&bg_memory)/1024.0/1024;
cerr<<"Memory: "<<memory_used<<"MB"<<endl;
return 0;
}拒绝 Top tree，从每一道题开始。