Advertisement
Guest User

Untitled

a guest
May 25th, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. ll n,t,u,v,a,b,s[100007][3];
  5. std::vector<ll> adj[100007];
  6. void dfs(ll cur, ll par, ll i){
  7.   s[i][cur] = 1;
  8.   printf("visiting %d\n", cur);
  9.   for(ll v: adj[cur])
  10.     if(par!=v) dfs(v, cur, i), s[i][cur]+=s[i][v];
  11. }
  12. int main(){
  13.   std::cin >> t;
  14.   while (t--) {
  15.     memset(s, 0, sizeof(s));
  16.     for(ll i = 0; i<=n; i++) adj[i].clear();
  17.     std::cin >> n >> a >> b;
  18.     for(ll i = 0; i<n-1; i++){
  19.       std::cin >> u >> v;
  20.       adj[u].push_back(v);
  21.       adj[v].push_back(u);
  22.     }
  23.     dfs(a,0,0);
  24.     for(ll i = 1; i<=n; i++){
  25.       // printf("s[0][%lld] = %lld\n", i, s[0][i]);
  26.     }
  27.     printf("\n\n");
  28.     dfs(b,0,1);
  29.     for(ll i = 1; i<=n; i++){
  30.       // printf("s[0][%lld] = %lld\n", i, s[1][i]);
  31.     }
  32.     ll res1 = (n-s[0][b])*s[0][b];
  33.     ll res2 = (n-s[1][a])*s[1][a];
  34.     ll res3 = s[0][b]*s[1][a];
  35.     // printf("res1 = %lld, res2 = %lld, res3 = %lld\n", res1, res2, res3);
  36.     std::cout << res1+res2-res3 << '\n';
  37.   }
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement