For a graph \(G\), we group all subsets of \(V(G)\) that can be painted with no more than \(K\) operations by the least number of operations required to paint a subset. There are no more than \(K + 1\) groups of subsets of \(V(G)\). For a subset \(U\) of \(V(G)\), let \(\delta_G(U)\) denote the least number of operations required to paint \(U\) in graph \(G\).

Let \(C_1\), \(C_2\) be connected subgraphs of \(G\) that satisfy the following conditions

• \(C_1\) and \(C_2\) are independent, that is, \(V(C_1) \cap V(C_2) = \O\).
• There is an edge \(e\) in \(G\) connecting \(C_1\) and \(C_2\), and \(e\) has a greater weight than any edge in \(C_1\) or \(C_2\).

Let \(C'\) denote the graph \(C_1 \cup C_2\)，let \(C\) denote the graph \(C_1 \cup C_2 \cup e\). Note that \(V(C) = V(C') = V(C_1) \cup V(C_2)\).

It is obvious that \(p(C') = p(C_1) p(C_2)\). Moreover, we have \(p(C) = p(C') - x^2 + x\). (why?)

The following facts holds

• For a subset \(U\) of \(V(C)\), if \(U \ne V(C)\), then \(\delta_C(U) = \delta_{C'}(U)\).
• \(\delta_C(V(C)) = 1\).
• \(\delta_{C'}(V(C)) = 2\).

Analysis of time complexity

Consider connecting two connected components \(C_1\) and \(C_2\), depending on whether their number of vertices are less than \(K\) or not:

• If both of them has \(K\) or more vertices. Such merge will occur no more than \(N/K\) times, and each of them can be computed in $O(K^2) $ time, so it costs a total of \(O(NK)\) time.
• If both of them has less than \(K\) vertices. Suppose that all cost required so far is considered when the size of connected component exceeds \(K\) for the first time. The time complexity of the process of connection is \(O(K^2)\), resulting in \(O(N/K)\) number of connected components with size \(\ge K\), so it will cost a total of \(O(NK)\) time.
• If one has \(K\) or more vertices while the other has less than \(K\). Assume \(|C_1| < K\), such a connection costs \(O(|C_1|K)\) time, and occurs at most once for a connected component with size less than \(K\) (and each vertex appears at most once in the smaller part of such merges). So it costs a total of \(O(NK)\) time.

Therefore, the overall time complexity is \(O(NK)\).

Code

#include <utils.hpp>
#include <dsu.hpp>
#include <m3.hpp>
#include <poly.hpp>

void solve() {
  INT(N, M, K);
  UnionFind dsu(N + 1);
  using poly = Poly<mint>;
  map<int, vii> e;
  rep (M) {
    INT(a, b, c);
    e[c].pb(a, b);
  }
  vector<poly> p(N + 1, {1, 1});
  FOR (c, ab, e) {
    vi old_roots;
    FOR (a, b, ab) {
      if (not dsu.same(a, b)) {
        old_roots.pb(dsu.root(b));
        dsu.unite(a, b);
      }
    }
    map<int, int> cnt;
    FOR (u, old_roots) {
      int r = dsu.root(u);
      cnt[r]++;
      p[r] *= p[u];
      if (SZ(p[r]) > K + 1)
        p[r].resize(K + 1);
    }

    FOR (root, C, cnt) {
      p[root][1] += 1;
      if (C + 1 <= K) {
        p[root][C + 1] -= 1;
      }
    }
  }

  poly prod = {1};
  up (i, 1, N)
    if (dsu.is_root(i)) {
      prod *= p[i];
      if (SZ(prod) > K + 1)
        prod.resize(K + 1);
    }
  pl(acc<mint>(prod));
}