求调
  • 板块AT_dp_v Subtree
  • 楼主mqmhaaaa1
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/7 21:10
  • 上次更新2024/8/7 21:56:30
查看原帖
求调
728448
mqmhaaaa1楼主2024/8/7 21:10
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+10;
ll n,mod;
ll to[N*2],nxt[N*2],bh[N],tot=1;
ll f[N],g[N];
ll qzj[N],hzj[N];
void add(ll u,ll v){
	to[++tot]=v;
	nxt[tot]=bh[u];
	bh[u]=tot;
} 
void dfs1(ll u,ll fa){
	f[u]=1;
	vector<ll>jb;
	for(ll i=bh[u];i;i=nxt[i]){
		ll v=to[i];
		if(v==fa)continue;
		dfs1(v,u);f[u]=(1LL*f[u]*(f[v]+1))%mod;
		jb.push_back(v);
	}
	ll sb1=1,sb2=1;
	for(ll i=0;i<jb.size();i++){
		ll v=jb[i];
		qzj[v]=sb1;
		sb1=(1LL*sb1*(f[v]+1))%mod;
	}
	for(ll i=jb.size()-1;i>=0;i--){
		ll v=jb[i];
		hzj[v]=sb2;
		sb2=(1LL*sb2*(f[v]+1))%mod;
	}
	return;
}
void dfs2(ll u,ll fa){
	if(fa==-1)g[u]=1;
	else g[u]=(1LL*g[fa]*qzj[u]*hzj[u]+1)%mod;
	for(ll i=bh[u];i;i=nxt[i]){
		if(to[i]!=fa)dfs2(to[i],u);
	}
	return;
}
int main(){
	cin>>n>>mod;
	for(ll i=1;i<n;i++){
		ll u,v;cin>>u>>v; 
		add(u,v);add(v,u);
	}
	dfs1(1,-1);
	dfs2(1,-1);
	for(int i=1;i<=n;i++){
		cout<<(1LL*f[i]*g[i])%mod<<endl;
	}
	return 0;
}


wa了,求调

2024/8/7 21:10
加载中...