或许是由于洛谷评测机过快的原因，我 $O(nR^2)$ 的代码竟然轻松通过了本题，请求加强数据。

https://www.luogu.com.cn/record/179165385

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define N 100005
#define M 105
using namespace std;
int n,m,ans1,ans2=1e9,f[N][M],pre[N][M],suf[N][M];
vector<pair<int,int> >v[N];
void dfs1(int k,int fa)
{
  for(auto now:v[k])
  {
    if(now.first==fa) continue;
    if(now.second==0) ans1=(ans1*(m-1))%mod;
    if(now.second==1) ans1=(ans1*m)%mod;
    dfs1(now.first,k);
  }
  return;
}

void dfs2(int k,int fa)
{
  for(int i=1;i<=m;i++) f[k][i]=i;
  for(auto now:v[k])
  {
    if(now.first==fa) continue;
    dfs2(now.first,k);
    if(now.second==0)
    {
      for(int i=1;i<=m;i++)
      {
        int minn=1e9;
        for(int j=1;j<=m;j++) if(i!=j) minn=min(minn,f[now.first][j]);
        f[k][i]+=minn;
      }
    }
    if(now.second==1)
    {
      for(int i=1;i<=m;i++)
      {
        int minn=1e9;
        for(int j=1;j<=m;j++) minn=min(minn,f[now.first][j]);
        f[k][i]+=minn;
      }
    }
    if(now.second==2)
    {
      for(int i=1;i<=m;i++) f[k][i]+=f[now.first][i];
    }
  }
  return;
}

signed main()
{
  ios::sync_with_stdio(0);
  cin>>n>>m;
  for(int i=1;i<n;i++)
  {
    int x,y,z;
    cin>>x>>y>>z;
    v[x].push_back({y,z});
    v[y].push_back({x,z});
  }
  ans1=m;
  dfs1(1,0);
  if(ans1==0)
  {
    cout<<0<<" "<<0;
    return 0;
  }
  dfs2(1,0);
  for(int i=1;i<=m;i++) ans2=min(ans2,f[1][i]);
  cout<<ans1<<" "<<ans2;
  return 0;
}