#505710 (C++14) No.1124 Earthquake Safety

• 問題: No.1124 Earthquake Safety
• ユーザー: e869120
• 提出日時: 2020-07-03 13:42:43
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 411 ms / 3,000 ms
• コード長: 2,984 bytes
• コンパイル時間: 979 ms
• コンパイル使用メモリ: 73,600 KB
• 実行使用メモリ: 87,808 KB
• 最終ジャッジ日時: 2024-09-16 17:08:36
• 合計ジャッジ時間: 16,200 ms
• ジャッジサーバーID （参考情報）: judge6 / judge4

ファイルパターン	結果
other	AC * 58

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)
const long long mod = 1000000007;
const long long inv2 = 500000004;
// 入出力
long long N, A[1 << 19], B[1 << 19];
long long Answer1, Answer2, Answer3A, Answer3B, Answer3C;
vector<int> X[1 << 19];
vector<int> Y[1 << 19];
// DP
int par[1 << 19];
long long dp1[1 << 19];
long long dp2[1 << 19];
long long dpr[1 << 19][4];
long long Eval[1 << 19];
void dfs1(int pos) {
    dp1[pos] += 1LL;
    for (int i : X[pos]) {
        if (dp1[i] != 0LL) continue;
        dfs1(i);
        par[i] = pos;
        Y[pos].push_back(i);
        dp1[pos] += dp1[i] * inv2 % mod;
        dp1[pos] %= mod;
    }
}
void dfs2(int pos) {
    for (int i : Y[pos]) {
        dp2[i] += dp2[pos] * inv2 % mod;
        dp2[i] += dp1[pos] * inv2 % mod;
        dp2[i] -= dp1[i] * (inv2 * inv2 % mod) % mod;
        dp2[i] = (dp2[i] + mod * mod) % mod;
        dfs2(i);
    }
}
void getEval() {
    for (int i = 1; i <= N; i++) {
        long long r = 0, s1 = 0, s2 = 0;
        for (int j : Y[i]) s1 += dp1[j] * inv2 % mod;
        for (int j : Y[i]) s2 += (dp1[j] * inv2 % mod) * (dp1[j] * inv2 % mod) % mod;
        s1 %= mod; s2 %= mod;
        r = s1 * s1 - s2;
        r = (r + mod * mod) % mod;
        Eval[i] = r * inv2 % mod;
    }
}
int main() {
    // Step #1. 入力
    scanf("%lld", &N);
    for (int i = 1; i <= N - 1; i++) scanf("%lld%lld", &A[i], &B[i]);
    for (int i = 1; i <= N - 1; i++) {
        X[A[i]].push_back(B[i]);
        X[B[i]].push_back(A[i]);
    }
    
    // Step #2. 全方位木DP
    dfs1(1);
    dfs2(1);
    // Step #3. [1], [2] の場合を求める
    Answer1 = N;
    getEval();
    for (int i = 1; i <= N; i++) Answer2 += (dp1[i] + mod - 1LL) % mod;
    for (int i = 1; i <= N; i++) Answer2 += Eval[i];
    Answer2 %= mod;
    // Step #4. [3] の場合 - Pattern A
    for (int i = 1; i <= N; i++) {
        long long r1 = (dp1[i] - 1LL);
        long long r2 = dp2[i];
        Answer3A += r1 * r2 % mod;
        Answer3A %= mod;
    }
    for (int i = 1; i <= N; i++) {
        Answer3A += Eval[i];
        Answer3A %= mod;
    }
    // Step #5. [3] の場合 - Pattern B
    for (int i = 1; i <= N; i++) {
        long long r1 = dp2[i];
        long long r2 = Eval[i];
        Answer3B += r1 * r2 % mod;
        Answer3B %= mod;
    }
    // Step #6. [3] の場合 - Pattern C
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= Y[i].size(); j++) { dpr[j][0] = 0; dpr[j][1] = 0; dpr[j][2] = 0; dpr[j][3] = 0; }
        dpr[0][0] = 1;
        for (int j = 0; j < Y[i].size(); j++) {
            for (int k = 0; k <= 3; k++) dpr[j + 1][k] = dpr[j][k];
            for (int k = 0; k <= 2; k++) {
                dpr[j + 1][k + 1] += dpr[j][k] * (dp1[Y[i][j]] * inv2 % mod) % mod;
                dpr[j + 1][k + 1] %= mod;
            }
        }
        Answer3C += dpr[Y[i].size()][3];
        Answer3C %= mod;
    }
    // Step #7. 出力
    long long Ret1 = Answer1;
    long long Ret2 = Answer2;
    long long Ret3 = (Answer3A + Answer3B + Answer3C) % mod;
    for (int i = 1; i <= N - 1; i++) { Ret1 *= 2LL; Ret1 %= mod; }
    for (int i = 1; i <= N - 1; i++) { Ret2 *= 2LL; Ret2 %= mod; }
    for (int i = 1; i <= N - 1; i++) { Ret3 *= 2LL; Ret3 %= mod; }
    cout << (1LL * Ret1 + 6LL * Ret2 + 6LL * Ret3) % mod << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX