Untitled
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