Untitled

 avatar
unknown
plain_text
a year ago
3.0 kB
5
Indexable
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
 
const double PI = 3.14159265358979;
const ll INF =  1e9 + 7;
const ll MOD = 1e9 + 7;
const ll nax = 2505;
const int LOG = 25;


void dfs1(int src, int pr, vector<int> &par, int dep, vector<int> &depth, vector<int> adj[]) {
    par[src] = pr;
    depth[src] = dep;

    for (int v: adj[src]) {
        if (v == pr) continue;

        dfs1(v, src, par, dep + 1, depth, adj);
    }
}

int dfs2(int src, int pr, vector<int> &par, int dep, int depCnt, vector<int> &depth, vector<int> adj[]) {
    par[src] = pr;
    depth[src] = dep;

    // cout << "src: = " << src << endl;
    int ans = 0;
    if (dep == depCnt) {
        // cout << "ans++: " << src << endl;
        ans++;
    }


    for (int v: adj[src]) {
        if (v == pr) continue;
        int childDepth = dfs2(v, src, par, dep + 1, depCnt, depth, adj);
        // cout << "childDepth: " << src << " " << v << " "<< childDepth << endl;
        ans += childDepth;
    }

    return ans;
}


void solve() {
    int n, x, y;
    cin >> n;

    if (n == 1) {
        cout << 1 << endl;
        return ;
    }
    vector<int> adj[n + 1];
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    x = 1; y = 1;
    vector<int> par(n + 1), depth(n + 1);
    dfs1(1, 0, par, 0, depth, adj);
    for (int i = 1; i <= n; i++) {
        if (depth[x] < depth[i]) {
            x = i;
        }
    }

    dfs1(x, 0, par, 0, depth, adj);
    for (int i = 1; i <= n; i++) {
        if (depth[y] < depth[i]) {
            y = i;
        }
    }

    int diameter = depth[y];
    // cout << "diameter = " << diameter<< endl;
    if (diameter & 1) {
        int c1, c2;

        c1 = y;
        int diameter1 = diameter / 2;
        while(diameter1--) {
            c1 = par[c1];
        }
        c2 = par[c1];

        // cout << c1 << " " << c2 << endl;

        int cnt1 = dfs2(c1, c2, par, 0, diameter / 2, depth, adj);
        int cnt2 = dfs2(c2, c1, par, 0, diameter / 2, depth, adj);

        // cout << cnt1 << " " << cnt2 << endl;
        ll ans = 1LL * cnt1 * cnt2;
        cout << ans << endl;
    } else {
        int c1 = y;
        int diameter1 = diameter / 2;
        while(diameter1--) {
            c1 = par[c1];
        }

        // cout << "c1: " << c1 << endl;        
        vector<int> cnts;
        ll sum = 0;
        for (auto v: adj[c1]) {
            // cout << "v: " << v <<endl;
            int cnt = dfs2(v, c1, par, 0, diameter / 2 - 1, depth, adj);
            cnts.push_back(cnt);
            sum += cnt;
        }

        ll ans = 0;
        for (int x: cnts) {
            ans += 1LL * x * (sum - x);
        }
        cout << ans / 2 << endl;
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // int t; cin >> t; while(t--)
    solve();
    return 0;
}
Editor is loading...
Leave a Comment