#572365 (C++14) No.1333 Squared Sum

• 問題: No.1333 Squared Sum
• ユーザー: penguinman
• 提出日時: 2020-10-30 04:26:25
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 457 ms / 2,000 ms
• コード長: 2,046 bytes
• コンパイル時間: 1,744 ms
• コンパイル使用メモリ: 184,012 KB
• 実行使用メモリ: 54,848 KB
• 最終ジャッジ日時: 2024-07-21 22:47:36
• 合計ジャッジ時間: 13,768 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

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

ソースコード

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
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using ll=long long;
//宣言、modpow
const int mod=1e9+7;
vector<vector<int>> edge,weight;
vector<ll> dp,subtree,sum;
vector<bool> flag;
ll ans=0;
ll modpow(ll x,ll y){
    ll ret=1;
    while(y){
        if(y&1){
            ret*=x;
            ret%=mod;
        }
        x*=x;
        x%=mod;
        y/=2;
    }
    return ret;
}
//dfs
void dfs(int now){
    flag[now]=1;
    for(int i=0;i<edge[now].size();i++){
        int next=edge[now][i];
        ll w=weight[now][i];
        if(flag[next]) continue;
        dfs(next);
        subtree[now]+=subtree[next];
        dp[now]+=dp[next]+subtree[next]*w%mod*w%mod+sum[next]*w%mod*2%mod;
        dp[now]%=mod;
        sum[now]+=sum[next]+w*subtree[next]%mod;
        sum[now]%=mod;
    }
}
//rerooting
void reroot(int now){
    flag[now]=0;
    ans+=dp[now];
    ans%=mod;
    for(int i=0;i<edge[now].size();i++){
        int next=edge[now][i];
        ll w=weight[now][i];
        if(!flag[next]) continue;
        ll dp2=dp[now]-dp[next]-subtree[next]*w%mod*w%mod-sum[next]*w%mod*2%mod;
        dp2%=mod;
        if(dp2<0) dp2+=mod;
        ll sum2=sum[now]-sum[next]-w*subtree[next]%mod;
        sum2%=mod;
        if(sum2<0) sum2+=mod;
        ll subtree2=subtree[now]-subtree[next];
        dp[next]+=dp2+subtree2*w%mod*w%mod+sum2*w%mod*2%mod;
        dp[next]%=mod;
        sum[next]+=sum2+w*subtree2%mod;
        sum[next]%=mod;
        subtree[next]+=subtree2;
        reroot(next);
    }
}
//main
int main(){
    //resize、input
    int N; cin>>N;
    edge.resize(N);
    weight.resize(N);
    dp.resize(N);
    subtree.resize(N,1);
    sum.resize(N);
    flag.resize(N);
    for(int i=1;i<N;i++){
        int x,y,z; cin>>x>>y>>z;
        edge[x-1].push_back(y-1);
        edge[y-1].push_back(x-1);
        weight[x-1].push_back(z);
        weight[y-1].push_back(z);
    }
    //求値、output
    dfs(0);
    reroot(0);
    ans*=modpow(2,mod-2);
    ans%=mod;
    cout<<ans<<endl;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX