競プロ日記

問題

ACコード

#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;
using Graph = vector;

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 
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;
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;
}

今回の学びはスタック領域は思ったよりも弱いということ・・・。
解き方は分からなかったので解説を見た。
思ったより単純でグラフの苦手意識が抜けてないのかなと思う。
方針だけ見て後は自力で！と思ったんだけど全然ACできない。
最初の3つのテストケースだけまさかのRE。
割り算とかやってないし範囲外アクセスしかないかなぁと悩み続け、範囲外アクセスの原因になりそうなところ(グラフの次数が1の頂点を探す部分)を変えて全部WAにするつもりで提出したら1つだけACで他WA。
おそらく答えが0になる部分なんだけろうけど、やはりここが間違いだった？と思うもどう考えても間違っているはずがない。
グラフが木なら次数が1の頂点が必ずあるはず。

そこから色々探って最終的に、Vectorのメモリ足りてないのでは？と思い立つ。
今までVectorには基本的にプリミティブ型やそのPair等しか入れていなかったが、今回は構造体を入れている。
最近作ったグラフ関連の構造体だ。
上限は10^5なのでもしやということでヒープ領域に取ってみるとREの2つがWAになり、おそらく答えが0になるテストケースがACになった。

残りの2つは、自分の実装が「根とその子は初期値として最初に計算して残りをDFSで計算する」という形だったため、n=1のときに根の子がないのにある体で初期化してしまっていたのが原因だった。


今までも10^5くらいのVectorはスタック領域に取っていたような気はするのだが、今回ついに問題になった。
世間ではグローバル変数はあまり使うべきではないと言われているが、自分もそれを学生時代に感じたため、基本的には全てローカル変数として宣言している。
学生時代には基礎だけで事足りており、その後プログラミングすることがなかったので、グローバル変数に対する考え方もその頃のままだった。
取れるメモリの上限に引っかかる問題を解決する方法はいくつかあるようだが、グローバル変数も手段の1つとして入れても良いかもしれない。
競技プログラミングにおいてはグローバル変数一択だとは思うが。