fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. /*#include<ext/pb_ds/assoc_container.hpp>
  4. #include<ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. /*template <typename T>
  7. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. */typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef long double ld;
  11. typedef pair<ll,ll> pl;
  12. typedef pair<int,int> pii;
  13.  
  14. #define LOCAL 0
  15. #define dbg(x) cout << #x << " is " << x << "\n"
  16. #define gll(x) scanf("%d",&x)
  17. #define gll2(x,y) scanf("%d%d",&x,&y)
  18. #define gll3(x,y,z) scanf("%d%d%d",&x,&y,&y)
  19. #define gllarr(arr,n) f(i,n) gll(arr[i]);
  20. #define sz(x) ((int)x.size())
  21. #define s(x) sort(x.begin(),x.end())
  22. #define all(v) v.begin(),v.end()
  23. #define rs(v) { s(v) ; r(v) ; }
  24. #define r(v) {reverse(all(v));}
  25. #define pb push_back
  26. #define F first
  27. #define S second
  28. #define f(i,n) for(int i=0;i<n;i++)
  29. #define fr(i,n) for(int i=n-1;i>=0;i--)
  30. #define rep(i,a,b) for(int i=a;i<=b;i++)
  31. #define repr(i,a,b) for(int i=a;i>=b;i--)
  32.  
  33. const ll mod = 1000000007;
  34. const ll inf = (ll)1e17;
  35. const ld eps = 1e-12;
  36. const ll N = (int)1e5+2;
  37. const ll LOGN = 19;
  38. const ld PI = 3.14159265358979323846;
  39. ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  40. ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  41. ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}
  42.  
  43. ll n,a,b;
  44. vector<ll> adj[N];
  45. ll sz[N];
  46. ll par[N];
  47.  
  48. void dfs(ll src,ll parent)
  49. {
  50.     sz[src] = 1;
  51.     for(ll i : adj[src]){
  52.         if(i != parent) {
  53.             par[i] = src;
  54.             dfs(i, src);
  55.             sz[src] += sz[i];
  56.         }
  57.     }
  58. }
  59.  
  60. int main() {
  61.     ios_base::sync_with_stdio(false);
  62.     cin.tie(NULL);
  63.     if (LOCAL) {
  64.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt", "r", stdin);
  65.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt", "w", stdout);
  66.     }
  67.     int t;
  68.     cin>>t;
  69.     while(t--)
  70.     {
  71.         cin>>n>>a>>b;
  72.         f(i,n+1){
  73.             par[i] = -1;
  74.             sz[i] = 0;
  75.             adj[i].clear();
  76.         }
  77.         f(i,n-1)
  78.         {
  79.             ll u,v;
  80.             cin>>u>>v;
  81.             adj[u].pb(v);
  82.             adj[v].pb(u);
  83.         }
  84.         par[a] = a;
  85.         dfs(a,a);
  86. //        rep(i,1,n+1)
  87. //            cout<<sz[i]<<" ";
  88. //        cout<<endl;
  89.         ll ver = par[b];
  90.         ll child = b;
  91.         ll ans = 0;
  92.         while(ver != a) {
  93.             ans += (ll)((ll)(sz[ver] - sz[child]) * (ll)(sz[a] - sz[ver]));
  94.             child = ver;
  95.             ver = par[ver];
  96.         }
  97.         //ll ans = ((ll)(sz[a] - sz[ver]) * (ll)(sz[ver] - sz[b]));
  98.         ans += (ll)((ll)(sz[a] - sz[b]) * (ll)sz[b]);
  99.         cout<<ans<<endl;
  100.     }
  101.     return 0;
  102. }
Success #stdin #stdout 0s 5412KB
comments (?)
stdin
copy 
1
5 1 3
1 2
2 3
2 4
4 5
stdout
copy 
7
https://ideone.com/Kn3zbJ
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!