社区讨论

求调,WA

AT_dp_v Subtree参与者 3已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@m5gltpjj
此快照首次捕获于
2025/01/03 18:20
去年
此快照最后确认于
2025/11/04 12:02
4 个月前
查看原帖
CF 上的双倍经验过了,但是这道题 WA 了,求调。
CPP
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e5+10;	
int n,mod;
int head[N],tot;
int dp[N],ans[N];
vector<int> pre[N],suf[N];

struct edge{
	int to,nex;
}e[N<<1];

inline void add(int u,int v)
{
	tot++;e[tot].nex=head[u];
	head[u]=tot;e[tot].to=v;
}

void dfs(int u,int fa)
{
	dp[u]=1;
	for(int i=head[u];i;i=e[i].nex)
	{
		int v=e[i].to;if(v==fa) continue;
		dfs(v,u);
		dp[u]=((dp[v]+1)%mod*dp[u])%mod;
	}
}

void dfs1(int u,int fa)
{
	ans[u]=1;
	for(int i=head[u];i;i=e[i].nex)
	{
		int v=e[i].to;
		ans[u]=(ans[u]*(dp[v]+1))%mod;
	}
	for(int i=head[u];i;i=e[i].nex)
	{
		int v=e[i].to;if(v==fa) continue;
		pre[u].push_back(dp[v]+1);
		suf[u].push_back(dp[v]+1);
	}
	int lp=pre[u].size();int ls=suf[u].size();
	for(int i=1;i<lp;i++) pre[u][i]=pre[u][i-1]*pre[u][i]%mod;
	for(int i=ls-2;i>=0;i--) suf[u][i]=suf[u][i+1]*suf[u][i]%mod;
	int j=0;
	for(int i=head[u];i;i=e[i].nex,j++)
	{
		int v=e[i].to;if(v==fa) continue;
		dp[u]=((dp[fa]+1)*((j>0?pre[u][j-1]:1ll)%mod*(j<ls-1?suf[u][j+1]:1ll)%mod)%mod)%mod;
		dfs1(v,u);
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>mod;
	for(int i=1;i<=n-1;i++)
	{
		int u,v;cin>>u>>v;
		add(u,v);add(v,u);
	}
	dfs(1,0);ans[1]=dp[1];	
	dfs1(1,0);
	for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
	return 0;
}

回复

5 条回复,欢迎继续交流。

正在加载回复...