真萌新求助今天的比赛
  • 板块学术版
  • 楼主ArusuMar1a
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/8/23 20:12
  • 上次更新2023/11/4 09:18:13
查看原帖
真萌新求助今天的比赛
380259
ArusuMar1a楼主2021/8/23 20:12

这次比赛的 B 题,为什么这样做不对呢?h

#include<bits\stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,mod=1e9+7;
int head[N],ver[N*2],net[N*2],edge[N*2],tot;
int n,flag;
ll ans1=1,ans2,f[N][3],R;
void add(int a,int b,int c){
	net[++tot]=head[a];
	head[a]=tot;
	ver[tot]=b;
	edge[tot]=c;
}
void dfs(int x,int fa,int op){
	if(op==1)ans1=(ans1*R)%mod;
	else if(op==0)ans1=(ans1*(R-1))%mod;
	for(int i=head[x];i;i=net[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs(v,x,edge[i]);
	}
}
void dfs2(int x,int fa){
	f[x][2]=2;
	f[x][1]=1;
	for(int i=head[x];i;i=net[i]){
		int v=ver[i];
		if(v==fa)continue;
		dfs2(v,x);
		if(edge[i]==0){
			f[x][2]+=f[v][1];
			f[x][1]+=f[v][2];
		}
		else if(edge[i]==1){
			f[x][2]+=min(f[v][1],f[v][2]);
			f[x][1]+=min(f[v][1],f[v][2]);
		}
		else {
			f[x][2]+=f[v][2];
			f[x][1]+=f[v][1];
		}
	}
}
int main(){
	scanf("%d%d",&n,&R);
	for(int i=1;i<n;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
		if(!c)flag=1;
	}
	if(flag&&R==1){
		printf("0 0");
		return 0;
	}
	dfs(1,0,1);
	dfs2(1,0);
	ans2=min(f[1][1],f[1][2]);
	printf("%lld %lld",ans1,ans2);
//	printf("0 0");
	return 0;
}
2021/8/23 20:12
加载中...