제출 #788628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
788628		WLZ	Star Trek (CEOI20_startrek)	C++17	100 / 100	65 ms	16360 KiB

startrek

#include <bits/stdc++.h>
using namespace std;
 
const long long MOD = (long long) 1e9 + 7;

int n;
long long d;
vector< vector<int> > g;
vector<bool> lose;
vector<int> lose_child, crit_win, crit_lose, crit;
long long l, e;

long long modpow(long long b, long long p) {
  if (p == 0) {
    return 1;
  }
  long long ans = modpow((b * b) % MOD, p / 2);
  if (p % 2 == 1) {
    ans = (ans * b) % MOD;
  }
  return ans;
}

long long inv(long long x) {
  return modpow(x, MOD - 2);
}

long long mul(long long x, long long y) {
  return (x * y) % MOD;
}

void dfs(int u, int p) {
  lose[u] = true;
  for (auto& v : g[u]) {
    if (v == p) {
      continue;
    }
    dfs(v, u);
    if (lose[v]) {
      lose[u] = false;
      lose_child[u]++;
    }
  }
}

void calc(int u) {
  if (lose[u]) {
    crit[u] = crit_win[u] + 1;
  } else {
    if (lose_child[u] == 1) {
      crit[u] = crit_lose[u];
    } else {
      crit[u] = 0;
    }
  }
}

void dfs2(int u, int p) {
  for (auto& v : g[u]) {
    if (v == p) {
      continue;
    }
    dfs2(v, u);
    if (lose[v]) {
      crit_lose[u] += crit[v];
    } else {
      crit_win[u] += crit[v];
    }
  }
  calc(u);
}

void reroot(int from, int to) {
  if (lose[to]) {
    lose_child[from]--;
    crit_lose[from] -= crit[to];
  } else {
    crit_win[from] -= crit[to];
  }
  if (lose_child[from] == 0) {
    lose[from] = true;
  }
  calc(from);
  if (lose[from]) {
    lose_child[to]++;
    crit_lose[to] += crit[from];
  } else {
    crit_win[to] += crit[from];
  }
  if (lose_child[to] > 0) {
    lose[to] = false;
  }
  calc(to);
}

void dfs3(int u, int p) {
  if (lose[u]) {
    l = (l + 1) % MOD;
    e = ((e - crit[u]) % MOD + MOD) % MOD;
  } else {
    e = (e + crit[u]) % MOD;
  }
  for (auto& v : g[u]) {
    if (v != p) {
      reroot(u, v);
      dfs3(v, u);
      reroot(v, u);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> d;
  g.resize(n + 1);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  lose.resize(n + 1);
  lose_child.assign(n + 1, 0);
  crit_win.resize(n + 1);
  crit_lose.resize(n + 1);
  crit.resize(n + 1);
  dfs(1, -1);
  dfs2(1, -1);
  dfs3(1, -1);
  long long ans = mul(l, mul(((modpow(n, 2 * d) - modpow(e, d)) % MOD + MOD) % MOD, inv(((modpow(n, 2) - e) % MOD + MOD) % MOD)));
  //cout << l << endl;
  //cout << ((modpow(n, 2 * d) - modpow(e, d)) % MOD + MOD) % MOD << endl;
  //cout << ((modpow(n, 2) - e) % MOD + MOD) % MOD << endl;
  ans = mul(ans, crit[1]);
  if (!lose[1]) {
    ans = ((modpow(n, 2 * d) - ans) % MOD + MOD) % MOD;
  } 
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 20 / 20
• Subtask 7: 20 / 20
• Subtask 8: 15 / 15