Submission #44081002

---

Source Code Expand

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define ll long long
#define ld long double

using namespace std;

#define F(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define vll vector<ll>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

// const int N = 100002;

const int mod = 1e9 + 7;

bool overflow(ll x, ll y) {
    return x > LLONG_MAX / y or ( y > LLONG_MAX / x);
}


template <typename T>
void trav(vector<T>v)
{
    for (auto i : v)
    {
        cout << i << ' ';
    }
    cout << '\n';
}


ll binpowmod(ll a, ll b, ll m = mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = ((res % m) * (a % m)) % m;
        }
        a = ((a % m) * (a % m)) % m;
        b >>= 1;
    }
    res %= m;
    return res;
}

ll fermat_inv(ll x) {
    return binpowmod(x, mod - 2);
}

bool primecheck(int x) {

    if (x <= 1)return false;

    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}



/*



    6,6 6,7 6,8
    7,6 7,7 7,8
    8,6 8,7 8,8

*/

ll fact[1000001];
ll finv[1000001];

void factorial(int n) {

    fact[0] = 1;
    finv[0] = 1;
    for (int i = 1; i < n; i++) {
        fact[i] = fact[i - 1] * i % mod;
        finv[i] = fermat_inv(fact[i]);
    }
}

ll calc(vll &a) {

    vll p = a;
    int sz = a.size();
    for (int i = 1; i < sz; i++)
    {
        p[i] += p[i - 1];
    }
    ll res = 0;
    for (int i = 1; i < sz - 1; i++) {
        res += (p[i - 1] * a[i] * (p[sz - 1] - p[i]));
    }
    return res;

}
vector<ll>adj[200001];
ll sub[200001];
int n;
ll fin;
void dfs(int src, int par) {

    sub[src] = 1;
    for (auto i : adj[src])
    {
        if (i != par) {
            dfs(i, src);
            sub[src] += sub[i];
        }
    }
    ll up = n - sub[src];
    // cout << src << " " << up << " " << '\n';

    long long ans = 0;
    long long sum = 0;
    int ct = 0;
    for (auto i : adj[src]) {
        if (i == par) {
            continue;
        }
        // cout << i << " ";
        ct++;
        ans += (sum * sub[i]);
        sum += sub[i];
    }

    if (ct > 2) {
        vector<ll>v;
        for (auto i : adj[src]) {
            if (i == par) {
                continue;
            }
            v.pb(sub[i]);
        }
        fin += calc(v);
    }
    // cout << '\n';
    // if (ct > 1)
    fin += up * ans;

    // cout << "count : " << ct << '\n';
}




int main()
{

    // ###w
    // ###w
    // ###w
    // wwww    5,5 5,6 5,7 5,8
    //        6,5 ###
    //        7,5 ###
    //        8,5 ###



    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // cout << "hello\n";
    int tc;
    // srand(time(NULL));
    tc = 1;
    // cin >> tc;
    // factorial(1000001);
    for (int w = 1; w <= tc; w++)
    {
        cin >> n;
        int x, y;
        for (int i = 0; i < n - 1; i++) {
            cin >> x >> y;
            adj[x].pb(y);
            adj[y].pb(x);
        }
        fin = 0;
        dfs(1, 0);
        cout << fin << '\n';
    }
    return 0;
}

Submission Info

Compile Error

./Main.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 

Judge Result