Mr. Nine and his love for mangoes

5.cpp

#include "bits/stdc++.h"
using namespace std;

#define endl '\n'
#define mp make_pair
#define int long long
#define pb push_back
#define vi vector<int>
#define vvi vector<vector<int>>
#define ar array
#define ll long long
#define ld long double
#define sza(x) ((int)x.size())
#define all(a) (a).begin(), (a).end()

const int max_n = 3e5 + 10;
const ll mod = 1e9 + 7;
const ll M = 1e9;
const ll inf = 1e9;
const ld eps = 1e-9;

void setio(string name = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (!name.empty()) {
    freopen((name + ".txt").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  } else {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
  }
}
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int hdx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int hdy[] = {-2, -1, 1, 2, 2, 1, -1, -2};
bool inside(int x, int y, int n, int m) {
  return x >= 0 && x < n && y >= 0 && y < m;
}
vector<vector<int>> adj;
vector<int> parent;

void dfs(int v, int par) {
  parent[v] = par;
  for (int u : adj[v]) {
    if (u == par)
      continue;
    dfs(u, v);
  }
}
int dfs1(int v, int par, int nxt) {
  int cnt = 1;
  for (int u : adj[v]) {
    if (u == par || u == nxt)
      continue;
    cnt += dfs1(u, v, nxt);
  }
  return cnt;
}
void solve() {
  int n;
  cin >> n;
  int s, e;
  cin >> s >> e;
  adj.resize(n + 1);
  parent.resize(n + 1);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  // Setting the start node as root and doing dfs to get parent of every node.
  dfs(s, -1);
  int end = e;
  int p_end = parent[e];
  while (p_end != s) {
    end = p_end;
    p_end = parent[end];
  }
  int c1 = dfs1(s, parent[s], end);
  int c2 = dfs1(e, parent[e], parent[e]);
  cout << n * (n - 1) - (c1 * c2) << endl;
}

int32_t main() {
  setio();
  int tc = 1;
  auto start_time = clock();
  // cin >> tc;
  for (int t = 1; t <= tc; t++) {
    // cout << "case #" << t << ": ";
    solve();
  }
  auto end_time = clock();
#ifndef ONLINE_JUDGE
  cout << "Time taken:" << (double)(end_time - start_time) / CLOCKS_PER_SEC
       << "s" << endl;
#endif
  return 0;
}