QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #659797 | #2328. Fruit on the Tree | masterhuang | AC ✓ | 23ms | 24044kb | C++23 | 580b | 2024-10-19 22:07:24 | 2024-10-19 22:07:26 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=3e5+5;
int n,sz[N];LL ans,f[N];
basic_string<int>E[N];
inline LL C2(int x){return (LL)x*(x-1)/2;}
void dfs(int x,int fa)
{
sz[x]=1;
for(int y:E[x]) if(y^fa)
dfs(y,x),ans+=f[x]*sz[y]+f[y]*sz[x],
sz[x]+=sz[y],f[x]+=f[y]+sz[y];
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
for(int i=1,u,v,w;i<n;i++) cin>>u>>v>>w,E[u]+=v,E[v]+=u;
return dfs(1,0),cout<<(LL)n*(n-1)*(n-2)/6-ans,0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 16468kb
input:
7 1 2 1 1 3 1 2 4 1 2 5 1 3 6 1 3 7 1
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 3ms
memory: 14756kb
input:
10 7 1 35966 7 4 12018 7 6 36983 6 8 90978 8 9 11522 8 5 5941 5 2 27692 2 3 3919 2 10 70217
output:
30
result:
ok single line: '30'
Test #3:
score: 0
Accepted
time: 13ms
memory: 24044kb
input:
100000 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11 1 11 12 1 12 13 1 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 1 19 20 1 20 21 1 21 22 1 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 1 28 29 1 29 30 1 30 31 1 31 32 1 32 33 1 33 34 1 34 35 1 35 36 1 36 37 1 37 38 1 38 39 1 39 40 ...
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 18ms
memory: 15560kb
input:
100000 40695 73595 18684 73595 13615 56138 13615 65545 7595 73595 19391 90277 73595 2353 23488 73595 26730 50193 2353 42541 19049 26730 28008 72631 28008 96282 33761 40695 76530 64056 40695 5872 13316 40695 61286 3279 2353 56072 90999 56072 87216 97221 96282 38177 22517 73595 50372 77342 61286 329 6...
output:
166569655489567
result:
ok single line: '166569655489567'
Test #5:
score: 0
Accepted
time: 23ms
memory: 16344kb
input:
100000 40695 73595 50158 73595 13615 75345 40695 65545 28277 40695 19391 16944 13615 2353 3229 40695 26730 67714 19391 42541 32571 13615 28008 53989 65545 96282 17259 26730 76530 81062 26730 5872 88464 28008 61286 76247 28008 56072 9728 65545 87216 88148 40695 38177 11692 42541 50372 15604 87216 329...
output:
166570073462944
result:
ok single line: '166570073462944'
Test #6:
score: 0
Accepted
time: 18ms
memory: 17084kb
input:
100000 40695 73595 16414 40695 13615 37512 73595 65545 29720 65545 19391 36735 13615 2353 91025 13615 26730 45672 2353 42541 98294 73595 28008 36873 13615 96282 72974 28008 76530 3711 40695 5872 80180 26730 61286 23001 26730 56072 99618 96282 87216 29359 61286 38177 41417 38177 50372 39260 61286 329...
output:
166562931233165
result:
ok single line: '166562931233165'
Test #7:
score: 0
Accepted
time: 22ms
memory: 15880kb
input:
100000 40695 73595 65279 40695 13615 78199 73595 65545 48959 40695 19391 59964 40695 2353 82970 2353 26730 85235 13615 42541 29740 26730 28008 35347 42541 96282 757 13615 76530 81715 73595 5872 63612 96282 61286 49215 28008 56072 12104 42541 87216 95428 26730 38177 867 87216 50372 53866 50372 329 99...
output:
166560315369978
result:
ok single line: '166560315369978'
Test #8:
score: 0
Accepted
time: 16ms
memory: 16684kb
input:
100000 40695 73595 14144 40695 13615 18886 40695 65545 51845 73595 19391 99546 73595 2353 58562 65545 26730 24798 26730 42541 61186 65545 28008 17468 19391 96282 28540 26730 76530 43366 73595 5872 47044 40695 61286 59076 76530 56072 24590 2353 87216 61497 40695 38177 60317 56072 50372 84825 61286 32...
output:
166564312191254
result:
ok single line: '166564312191254'
Test #9:
score: 0
Accepted
time: 20ms
memory: 16984kb
input:
100000 40695 73595 45618 40695 13615 21740 73595 65545 72527 40695 19391 26213 19391 2353 38303 13615 26730 42319 2353 42541 58355 42541 28008 98826 28008 96282 12038 96282 76530 44019 42541 5872 5839 73595 61286 32044 76530 56072 26966 96282 87216 52424 87216 38177 33139 65545 50372 23087 87216 329...
output:
166557579456100
result:
ok single line: '166557579456100'
Test #10:
score: 0
Accepted
time: 20ms
memory: 14760kb
input:
100000 40695 73595 94483 40695 13615 62427 73595 65545 91766 73595 19391 65795 13615 2353 13895 40695 26730 81882 13615 42541 89801 2353 28008 97300 19391 96282 39821 65545 76530 5670 42541 5872 89271 19391 61286 41905 61286 56072 39452 42541 87216 18493 28008 38177 92589 13615 50372 54046 73595 329...
output:
166568450039301
result:
ok single line: '166568450039301'
Test #11:
score: 0
Accepted
time: 15ms
memory: 16740kb
input:
100000 40695 73595 43348 40695 13615 3114 40695 65545 94652 13615 19391 89024 40695 2353 5840 19391 26730 21445 26730 42541 21247 13615 28008 79421 73595 96282 67604 42541 76530 83674 42541 5872 72703 42541 61286 51766 73595 56072 35585 2353 87216 84562 13615 38177 52039 13615 50372 85005 2353 329 4...
output:
166565799032561
result:
ok single line: '166565799032561'
Test #12:
score: 0
Accepted
time: 23ms
memory: 16328kb
input:
100000 40695 73595 92213 40695 13615 43801 40695 65545 97538 65545 19391 12253 65545 2353 81432 73595 26730 77361 65545 42541 69046 40695 28008 61542 42541 96282 95387 73595 76530 45325 42541 5872 56135 76530 61286 61627 40695 56072 48071 65545 87216 50631 5872 38177 11489 73595 50372 99611 73595 32...
output:
166570135862862
result:
ok single line: '166570135862862'
Test #13:
score: 0
Accepted
time: 16ms
memory: 16884kb
input:
100000 40695 73595 18136 40695 13615 49905 13615 65545 85257 73595 19391 58540 13615 2353 71012 65545 26730 90360 73595 42541 98644 73595 28008 56528 40695 96282 56906 26730 76530 42023 26730 5872 9161 2353 61286 94606 65545 56072 74325 40695 87216 30505 42541 38177 52822 40695 50372 74948 73595 329...
output:
166563219000296
result:
ok single line: '166563219000296'
Test #14:
score: 0
Accepted
time: 3ms
memory: 14764kb
input:
1
output:
0
result:
ok single line: '0'
Test #15:
score: 0
Accepted
time: 3ms
memory: 13280kb
input:
2 1 2 1
output:
0
result:
ok single line: '0'
Test #16:
score: 0
Accepted
time: 0ms
memory: 15984kb
input:
3 1 2 3 2 3 4
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 3ms
memory: 15976kb
input:
4 1 2 3 1 3 4 1 4 5
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 0ms
memory: 14992kb
input:
4 1 2 3 2 3 4 3 4 5
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 2ms
memory: 15476kb
input:
10 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 9 10 1 10 11
output:
84
result:
ok single line: '84'
Test #20:
score: 0
Accepted
time: 0ms
memory: 13100kb
input:
5 1 2 1 1 3 1 2 4 1 2 5 1
output:
2
result:
ok single line: '2'