109C - Lucky Tree - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define int long long 



int p[200005], sum[200005], n, res;

int find(int x)
{
  if (p[x] != x)
    p[x] = find(p[x]);
  return p[x];
}

void merge(int a,int b)
{
  a = find(a), b = find(b);
  if (a == b)
    return;
  p[a] = b;
  sum[b] += sum[a];
}

bool ck(int x)
{
  while (x)
  {
    if (x % 10 != 7 && x % 10 != 4)
      return false;
    x /= 10;
  }
  return true;
}

int32_t main()
{
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    p[i] = i;
    sum[i] = 1;
  }
  for (int i = 1; i < n; i++)
  {
    int a, b, c;
    cin >> a >> b >> c;
    if (!ck(c))
      merge(a, b);
  }

  for (int i = 1; i <= n; i++)
  {
    int t = n - sum[find(i)];
    res += t * (t - 1);
  }
  cout << res << endl;
}