Untitled

unknown
plain_text
2 months ago
3.0 kB
0
Indexable
Never
```#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;

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++;
}

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 ;
}
for (int i = 1; i < n; i++) {
cin >> x >> y;
}

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;
// 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;
}```