Submission #59488245

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
typedef pair<int,int> P;
constexpr ll mod = 998244353;
typedef modint998244353 mi;

vector<int>G[100005];
ll child[100005];
int n;

void dfs(int now,int par,ll &sum){
    for(auto e:G[now]){
        if(e==par)continue;
        dfs(e,now,sum);
        child[now]+=child[e];
        sum+=child[e]*(n-child[e]);
    }
    child[now]++;
}

int main(){
    cin>>n;
    rep(i,n-1){
        int a,b;cin>>a>>b;
        a--;b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    ll sum=0;
    dfs(0,-1,sum);
    cout<<sum<<endl;

}

Submission Info

Submission Time
Task 039 - Tree Distance（★5）
User Rho17
Language C++ 20 (gcc 12.2)
Score 5
Code Size 782 Byte
Status AC
Exec Time 49 ms
Memory 9996 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 5 / 5
Status
AC × 3
AC × 34
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 10_random_small_00.txt, 10_random_small_01.txt, 10_random_small_02.txt, 10_random_small_03.txt, 10_random_small_04.txt, 10_random_small_05.txt, 10_random_small_06.txt, 10_random_small_07.txt, 10_random_small_08.txt, 10_random_small_09.txt, 11_random_large_00.txt, 11_random_large_01.txt, 11_random_large_02.txt, 11_random_large_03.txt, 11_random_large_04.txt, 11_random_large_05.txt, 11_random_large_06.txt, 11_random_large_07.txt, 11_random_large_08.txt, 11_random_large_09.txt, 20_random_max_00.txt, 20_random_max_01.txt, 20_random_max_02.txt, 20_random_max_03.txt, 20_random_max_04.txt, 20_random_max_05.txt, 20_random_max_06.txt, 30_uni_00.txt, 30_uni_01.txt, 40_path_00.txt, 40_path_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 2 ms 3584 KiB
00_sample_01.txt AC 1 ms 3536 KiB
00_sample_02.txt AC 1 ms 3576 KiB
10_random_small_00.txt AC 1 ms 3572 KiB
10_random_small_01.txt AC 2 ms 3444 KiB
10_random_small_02.txt AC 1 ms 3516 KiB
10_random_small_03.txt AC 1 ms 3508 KiB
10_random_small_04.txt AC 1 ms 3732 KiB
10_random_small_05.txt AC 1 ms 3640 KiB
10_random_small_06.txt AC 1 ms 3576 KiB
10_random_small_07.txt AC 1 ms 3636 KiB
10_random_small_08.txt AC 1 ms 3576 KiB
10_random_small_09.txt AC 1 ms 3552 KiB
11_random_large_00.txt AC 1 ms 3572 KiB
11_random_large_01.txt AC 3 ms 3880 KiB
11_random_large_02.txt AC 3 ms 3956 KiB
11_random_large_03.txt AC 4 ms 4008 KiB
11_random_large_04.txt AC 3 ms 3916 KiB
11_random_large_05.txt AC 2 ms 3756 KiB
11_random_large_06.txt AC 3 ms 3844 KiB
11_random_large_07.txt AC 4 ms 4164 KiB
11_random_large_08.txt AC 4 ms 4224 KiB
11_random_large_09.txt AC 2 ms 3780 KiB
20_random_max_00.txt AC 48 ms 9888 KiB
20_random_max_01.txt AC 47 ms 9924 KiB
20_random_max_02.txt AC 48 ms 9912 KiB
20_random_max_03.txt AC 47 ms 9928 KiB
20_random_max_04.txt AC 49 ms 9996 KiB
20_random_max_05.txt AC 47 ms 9932 KiB
20_random_max_06.txt AC 47 ms 9892 KiB
30_uni_00.txt AC 40 ms 9976 KiB
30_uni_01.txt AC 42 ms 9776 KiB
40_path_00.txt AC 2 ms 3720 KiB
40_path_01.txt AC 5 ms 4760 KiB