UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214272#2763. 幻想乡的拜访laiyishi302163ms67620kbC++11568b2024-11-16 22:16:102024-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'