WA12个点,悬关求调
  • 板块AT_dp_v Subtree
  • 楼主114514xxx
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/11/18 11:23
  • 上次更新2024/11/18 15:47:05
查看原帖
WA12个点,悬关求调
749175
114514xxx楼主2024/11/18 11:23
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=1e5+25;
int n,m;
int f1[N],f2[N];
struct Edge{
    int to,next;
}edge[N*2];
int head[N],cnt,pre_mul[N],suf_mul[N];
inline void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
inline int mul(int i,int fa,int val){
	if(!i)return 1;
	int v=edge[i].to;
	pre_mul[v]=val;
	if(v==fa)
		return suf_mul[v]=mul(edge[i].next,fa,val)%m;
	suf_mul[v]=mul(edge[i].next,fa,(val*(f1[v]+1))%m)%m;
	return ((suf_mul[v]%m)*((f1[v]+1)%m))%m;
}
inline void dfs(int u,int fa){
    f1[u]=1;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        dfs(v,u);
        f1[u]=(f1[u]*(f1[v]+1))%m;
        //f1[u]%=m;
    }
    mul(head[u],fa,1);
}
inline void dp(int u,int fa,int ff){
    if(u!=1){
        ff=((ff+1)*suf_mul[u]*(pre_mul[u]))%m;
        f2[u]=(f1[u]*(ff+1))%m;
        ff%=m;
    }
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa)continue;
        dp(v,u,ff);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int u,v;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    f2[1]=f1[1]%m;
    dp(1,0,0);
    for(int i=1;i<=n;i++)
        cout<<f2[i]%m<<"\n";
}

2024/11/18 11:23
加载中...