ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#214272 | #2763. 幻想乡的拜访 | laiyishi | 30 | 2163ms | 67620kb | C++11 | 568b | 2024-11-16 22:16:10 | 2024-11-16 23:14:11 |
answer
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,a[1000005],dp[1000005],sz[100005];
vector<int>g[1000005];
int ret;
void dfs(int u,int fa){
for(int v:g[u]){
if(v==fa)continue;
dfs(v,u);
ret=((ret+1ll*dp[u]*sz[v]%mod)%mod+1ll*(dp[v]+sz[v])*sz[u]%mod)%mod;
sz[u]+=sz[v];
dp[u]=((dp[u]+dp[v])%mod+sz[v])%mod;
}
sz[u]+=u;
ret=(ret+dp[u]*u%mod)%mod;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;scanf("%d%d",&u,&v);
g[u].push_back(v);g[v].push_back(u);
}
dfs(1,-1);
printf("%d\n",ret);
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 9ms
memory: 24684kb
input:
200 20 160 90 160 5 90 78 90 186 90 149 90 104 78 136 160 106 78 100 106 168 90 30 5 85 136 28 149 1...
output:
104425891
result:
ok single line: '104425891'
Test #2:
score: 10
Accepted
time: 9ms
memory: 24680kb
input:
200 49 91 20 91 147 91 131 20 36 131 9 131 51 147 173 51 32 36 169 51 180 51 2 91 133 2 72 20 14 169...
output:
145567217
result:
ok single line: '145567217'
Test #3:
score: 10
Accepted
time: 3ms
memory: 24680kb
input:
200 44 72 187 72 115 72 124 115 80 124 34 72 22 115 162 34 123 44 93 22 135 80 5 124 112 72 76 187 3...
output:
226420652
result:
ok single line: '226420652'
Test #4:
score: 0
Wrong Answer
time: 7ms
memory: 24804kb
input:
3000 940 1649 220 1649 1438 1649 2264 1649 1467 940 1825 220 1646 940 571 220 1419 220 2509 1438 264...
output:
20926201
result:
wrong answer 1st lines differ - expected: '781596579', found: '20926201'
Test #5:
score: 0
Wrong Answer
time: 3ms
memory: 24816kb
input:
3000 2156 216 2422 2156 2801 216 2504 2156 2701 2156 2582 2801 1558 2156 864 2582 737 864 2919 1558 ...
output:
729530438
result:
wrong answer 1st lines differ - expected: '236427659', found: '729530438'
Test #6:
score: 0
Wrong Answer
time: 3ms
memory: 24808kb
input:
3000 2966 2885 2657 2885 2613 2966 1686 2613 2803 2885 191 2657 2824 2657 675 2657 2693 191 2798 191...
output:
806107919
result:
wrong answer 1st lines differ - expected: '688220644', found: '806107919'
Test #7:
score: 0
Wrong Answer
time: 541ms
memory: 67600kb
input:
1000000 984750 990109 970095 984750 996126 970095 998081 990109 987074 970095 962711 970095 916630 9...
output:
-19954042
result:
wrong answer 1st lines differ - expected: '192557796', found: '-19954042'
Test #8:
score: 0
Wrong Answer
time: 527ms
memory: 67404kb
input:
1000000 947305 936749 948062 947305 970449 947305 988744 948062 998703 988744 986194 947305 997762 9...
output:
182702470
result:
wrong answer 1st lines differ - expected: '160385007', found: '182702470'
Test #9:
score: 0
Wrong Answer
time: 522ms
memory: 67620kb
input:
1000000 952012 962256 982471 962256 955412 952012 953636 962256 991390 952012 998704 953636 999294 9...
output:
-100663156
result:
wrong answer 1st lines differ - expected: '308556344', found: '-100663156'
Test #10:
score: 0
Wrong Answer
time: 539ms
memory: 67572kb
input:
1000000 900864 972452 986047 900864 953966 972452 977801 986047 997024 972452 954755 953966 999240 9...
output:
311754493
result:
wrong answer 1st lines differ - expected: '201471911', found: '311754493'