【2】做题心得 - 2025 NOIP #65 - T3【数据结构】【矩阵快速幂】【线段树合并】

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+10,M=2e7+10;
const ll P=998244353;
int n,x,y,sub;
ll a[N],ans[N];
vector<int>e[N];
struct mtr{
	ll a[2][2];
	mtr(){ a[0][0]=a[0][1]=a[1][0]=a[1][1]=0; }
} t[M],fib[2],pv; // 0+ 1-
ll qp(ll a,ll b){
	ll res=1;
	for(;b;b>>=1,a=(a*a)%P)	
		if(b&1) res=(res*a)%P;
	return res;
}
mtr add(mtr x,mtr y){
	mtr ans=mtr();
	for(int i=0;i<2;i++)for(int j=0;j<2;j++)
		ans.a[i][j]=(x.a[i][j]+y.a[i][j])%P;
	return ans;
}
mtr mul(mtr x,mtr y){
	mtr ans=mtr();
	for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++)
		ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j]%P)%P;
	return ans;
}
mtr qp(mtr x,ll b){
	mtr ans=mtr();
	ans.a[0][0]=ans.a[1][1]=1;
	for(;b;b>>=1,x=mul(x,x)) if(b&1) ans=mul(ans,x);
	return ans;
}
int tot,mrd[M],top; 	
int rt[2][N],ls[M],rs[M];
void merge(int &u,int &v,int l,int r){
	if(!v) return;
	if(!u) return u=v, void(0);
	mrd[++top]=v;
	if(l==r) return t[u]=add(t[u],t[v]), void(0);
	int mid=(l+r)>>1;
	merge(ls[u],ls[v],l,mid);
	merge(rs[u],rs[v],mid+1,r);
	t[u]=add(t[u],t[v]);
}
void query(int u,int v,int l,int r,int uv){
	if(!u||!v) return;
	if(l==r) return;
	int mid=(l+r)>>1;
	(ans[uv]+=mul(mul(pv,t[ls[v]]),t[rs[u]]).a[0][1])%=P;
	query(ls[u],ls[v],l,mid,uv);
	query(rs[u],rs[v],mid+1,r,uv);
	return;
}
void update(int &p,int l,int r,int pos,mtr uv){
	if(!p){
		if(top) p=mrd[top--], t[p]=mtr(), ls[p]=rs[p]=0;
		else p=++tot;
	}
	if(l==r) return t[p]=add(t[p],uv), void(0);
	int mid=(l+r)>>1;
	if(pos<=mid) update(ls[p],l,mid,pos,uv);
	else         update(rs[p],mid+1,r,pos,uv);
	t[p]=add(t[ls[p]],t[rs[p]]);
}
int d[N],l,na[N];
void dfs(int p,int fa){
	update(rt[0][p],1,l,na[p],qp(fib[0],a[p]));
	update(rt[1][p],1,l,na[p],qp(fib[1],a[p]));
	for(auto v:e[p])if(v^fa){
		dfs(v,p);
		query(rt[0][p],rt[1][v],1,l,p);
		query(rt[0][v],rt[1][p],1,l,p);
		ans[p]=(ans[p]+ans[v])%P;
		merge(rt[0][p],rt[0][v],1,l);
		merge(rt[1][p],rt[1][v],1,l);
	}
	return;
}
int main(){
	freopen("sam.in","r",stdin);
	freopen("sam.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>x>>y>>sub;
	for(int i=1;i<=n;i++)
		cin>>a[i],
		d[i]=a[i];
	sort(d+1,d+n+1);
	l=unique(d+1,d+n+1)-d-1;
	for(int i=1;i<=n;i++)
		na[i]=lower_bound(d+1,d+l+1,a[i])-d;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	fib[0].a[0][0]=x, fib[0].a[0][1]=1,
	fib[0].a[1][0]=y, fib[0].a[1][1]=0;
	fib[1].a[0][0]=0, fib[1].a[0][1]=qp(y,P-2),
	fib[1].a[1][0]=1, fib[1].a[1][1]=(P-x)*qp(y,P-2)%P;
	pv.a[0][0]=1, pv.a[0][1]=0,
	pv.a[1][0]=0, pv.a[1][1]=0;
	dfs(1,0);
	for(int i=1;i<=n;i++)
		cout<<ans[i]<<"\n";
	return 0;
}