結果
問題 | No.1103 Directed Length Sum |
ユーザー | rokahikou1 |
提出日時 | 2020-07-30 17:43:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,050 ms / 3,000 ms |
コード長 | 3,633 bytes |
コンパイル時間 | 1,061 ms |
コンパイル使用メモリ | 103,608 KB |
実行使用メモリ | 175,232 KB |
最終ジャッジ日時 | 2024-07-04 10:28:45 |
合計ジャッジ時間 | 13,168 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 802 ms
175,232 KB |
testcase_03 | AC | 497 ms
54,216 KB |
testcase_04 | AC | 579 ms
38,784 KB |
testcase_05 | AC | 1,050 ms
64,768 KB |
testcase_06 | AC | 363 ms
26,368 KB |
testcase_07 | AC | 71 ms
8,704 KB |
testcase_08 | AC | 118 ms
11,736 KB |
testcase_09 | AC | 45 ms
6,784 KB |
testcase_10 | AC | 167 ms
14,808 KB |
testcase_11 | AC | 645 ms
41,984 KB |
testcase_12 | AC | 364 ms
26,624 KB |
testcase_13 | AC | 177 ms
15,232 KB |
testcase_14 | AC | 32 ms
5,760 KB |
testcase_15 | AC | 287 ms
21,376 KB |
testcase_16 | AC | 728 ms
46,848 KB |
testcase_17 | AC | 760 ms
48,640 KB |
testcase_18 | AC | 168 ms
14,804 KB |
testcase_19 | AC | 653 ms
43,008 KB |
testcase_20 | AC | 54 ms
7,424 KB |
testcase_21 | AC | 105 ms
10,880 KB |
testcase_22 | AC | 528 ms
35,648 KB |
testcase_23 | AC | 303 ms
22,656 KB |
ソースコード
#include <algorithm> #include <cmath> #include <cstdint> #include <cstdio> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define rep(i, n) for(int(i) = 0; (i) < (n); (i)++) #define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++) #define All(v) (v).begin(), (v).end() #define pb push_back #define MP(a, b) make_pair((a), (b)) using ll = long long; using pii = pair<int, int>; using pll = pair<ll, ll>; const int INF = 1 << 30; const ll LINF = 1LL << 60; const int MOD = 1e9 + 7; using Tree = vector<vector<int>>; ll dfs(int v, int p, int d, const Tree &G, vector<ll> &childs, vector<ll> &depth) { ll num = 1; depth[v] = d; if(G[v].size() == 0) { return childs[v] = 1; } for(auto nv : G[v]) { if(nv == p) continue; num += dfs(nv, v, d + 1, G, childs, depth); } return childs[v] = num; } template <uint_fast64_t MOD> class ModInt { using u64 = uint_fast64_t; public: u64 val; ModInt(const u64 x = 0) : val(x % MOD) {} constexpr u64 &value() { return val; } constexpr ModInt operator-() { return val ? MOD - val : 0; } constexpr ModInt operator+(const ModInt &rhs) const { return ModInt(*this) += rhs; } constexpr ModInt operator-(const ModInt &rhs) const { return ModInt(*this) -= rhs; } constexpr ModInt operator*(const ModInt &rhs) const { return ModInt(*this) *= rhs; } constexpr ModInt operator/(const ModInt &rhs) const { return ModInt(*this) /= rhs; } constexpr ModInt &operator+=(const ModInt &rhs) { val += rhs.val; if(val >= MOD) { val -= MOD; } return *this; } constexpr ModInt &operator-=(const ModInt &rhs) { if(val < rhs.val) { val += MOD; } val -= rhs.val; return *this; } constexpr ModInt &operator*=(const ModInt &rhs) { val = val * rhs.val % MOD; return *this; } constexpr ModInt &operator/=(const ModInt &rhs) { *this *= rhs.inv(); return *this; } constexpr bool operator==(const ModInt &rhs) { return this->a == rhs.a; } constexpr bool operator!=(const ModInt &rhs) { return this->a != rhs.a; } friend constexpr ostream &operator<<(ostream &os, const ModInt<MOD> &x) { return os << x.val; } friend constexpr istream &operator>>(istream &is, ModInt<MOD> &x) { return is >> x.val; } constexpr ModInt inv() const { return ModInt(*this).pow(MOD - 2); } constexpr ModInt pow(ll e) const { u64 x = 1, p = val; while(e > 0) { if(e % 2 == 0) { p = (p * p) % MOD; e /= 2; } else { x = (x * p) % MOD; e--; } } return ModInt(x); } }; int main() { int N; cin >> N; vector<pii> edges(N - 1); Tree G(N); vector<bool> is_root(N, true); rep(i, N - 1) { int a, b; cin >> a >> b; a--, b--; edges[i] = MP(a, b); G[a].pb(b); is_root[b] = false; } int root = 0; rep(i, N) { if(is_root[i]) { root = i; break; } } vector<ll> childs(N), depth(N); dfs(root, -1, 1, G, childs, depth); using mint = ModInt<MOD>; mint res = 0; rep(i, N - 1) { ll m = childs[edges[i].second]; res += mint(m * (depth[edges[i].first])); } cout << res << endl; return 0; }