Submission #7357403

---

Source Code Expand

#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP()(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) (x).begin(), (x).end()
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
  #define debug(x) cerr << #x " => " << x << endl
#else
  #define debug(x) 0
#endif
using lint = long long;
constexpr int    INF  = 1 << 30;
constexpr lint   INFL = 1LL << 62;
constexpr int    MOD  = (int)1e9 + 7;
constexpr double EPS  = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(void) {}
  Edge(int src, int dst, Weight weight) : src(src), dst(dst), weight(weight) {}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

Graph edges_to_graph(const Edges &edges, const int vertices_num, const bool directed = true) {
  Graph ret(vertices_num);
  for (const auto &e : edges) {
    ret[e.src].push_back(e);
    if (!directed) ret[e.dst].push_back(Edge(e.dst, e.src, e.weight));
  }
  return ret;
}

template <long long mod_num>
class ModInt {
  long long n_;

  public:
  constexpr ModInt(const long long num = 0) : n_(num % mod_num) {}
  constexpr const long long&value() const { return n_; }
  constexpr bool   operator==(const ModInt &r) const { return this->n_ == r.n_; }
  constexpr bool   operator==(const long long &r) const { return this->n_ == r; }
  constexpr bool   operator!=(const ModInt &r) const { return this->n_ != r.n_; }
  constexpr bool   operator!=(const long long &r) const { return this->n_ != r; }
  constexpr bool   operator<(const ModInt &r) const { return this->n_ < r.n_; }
  constexpr bool   operator<(const long long &r) const { return this->n_ < r; }
  constexpr bool   operator>(const ModInt &r) const { return this->n_ > r.n_; }
  constexpr bool   operator>(const long long &r) const { return this->n_ > r; }
  constexpr bool   operator<=(const ModInt &r) const { return this->n_ <= r.n_; }
  constexpr bool   operator<=(const long long &r) const { return this->n_ <= r; }
  constexpr bool   operator>=(const ModInt &r) const { return this->n_ >= r.n_; }
  constexpr bool   operator>=(const long long &r) const { return this->n_ >= r; }
  constexpr ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
  constexpr ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
  constexpr ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
  constexpr ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
  constexpr ModInt operator+(const long long &r) const { return ModInt(*this) += ModInt(r); }
  constexpr ModInt operator-(const long long &r) const { return ModInt(*this) -= ModInt(r); }
  constexpr ModInt operator*(const long long &r) const { return ModInt(*this) *= ModInt(r); }
  constexpr ModInt operator/(const long long &r) const { return ModInt(*this) /= ModInt(r); }
  friend ModInt operator+(const long long &l, const ModInt &r) { return ModInt(l) += r; }
  friend ModInt operator-(const long long &l, const ModInt &r) { return ModInt(l) -= r; }
  friend ModInt operator*(const long long &l, const ModInt &r) { return ModInt(l) *= r; }
  friend ModInt operator/(const long long &l, const ModInt &r) { return ModInt(l) /= r; }
  constexpr ModInt &operator++() { return *this += 1; }
  constexpr ModInt &operator--() { return *this -= 1; }
  constexpr ModInt &operator+=(const ModInt &r) {
    n_ += r.n_;
    if (n_ >= mod_num) n_ -= mod_num;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &r) {
    if (n_ < r.n_) n_ += mod_num;
    n_ -= r.n_;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &r) {
    n_ = n_ * r.n_ % mod_num;
    return *this;
  }
  constexpr ModInt &operator/=(ModInt r) {
    long long exp = mod_num - 2;
    while (exp) {
      if (exp & 2) *this *= r;
      r   *= r;
      exp /= 2;
    }
    return *this;
  }
  friend istream &operator>>(istream &is, ModInt<mod_num> &r) {
    is >> r.n_;
    r.n_ %= r.mod_num;
    return is;
  }
  friend ostream &operator<<(ostream &os, const ModInt<mod_num> &r) { return os << r.n_; }
  explicit operator int() const { return n_; }
  explicit operator long long() const { return n_; }
  explicit operator double() const { return n_; }
};

using mint = ModInt<MOD>;
void dfs(const Graph &g, int v, int p, int k, mint &sum) {
  if (g[v].size() == 1) return;
  rep (i, g[v].size() - 1) {
    sum *= k - 2 - i;
  }
  for (const auto &es : g[v]) {
    if (es.dst == p) continue;
    dfs(g, es.dst, v, k, sum);
  }
}
Graph graph(100001);
Edges edges(100001);
int main(void) {
  int n, k;
  cin >> n >> k;
  // Edges edges(n - 1);
  rep (i, n - 1) {
    cin >> edges[i].src >> edges[i].dst;
    --edges[i].src;
    --edges[i].dst;
  }
  // Graph graph = edges_to_graph(edges, n, false);
  rep (i, n - 1) {
    graph[edges[i].src].push_back(edges[i]);
    graph[edges[i].dst].push_back(Edge(edges[i].dst, edges[i].src, edges[i].weight));
  }
  int start, next;
  rep (i, n) {
    if (graph[i].size() == 1) {
      start = i;
      next  = graph[i][0].dst;
      break;
    }
  }
  mint sum = k;
  if (n > 1) {
    sum *= (k - 1);
    dfs(graph, next, start, k, sum);
  }
  cout << sum << endl;
  return 0;
}

Submission Info

Judge Result