Untitled
unknown
plain_text
a year ago
3.0 kB
6
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