这次比赛的 B 题,为什么这样做不对呢?
#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;
}