fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <iomanip>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  7. using namespace std;
  8. #define ll long long
  9. #define pb push_back
  10. #define all(a)  a.begin(),a.end()
  11. #define death ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  12.  
  13. ////////////////////////////////////global variables//////////////////////////////////////////////////
  14. map<int ,vector<int>> adj;
  15. map<int, bool> vis;
  16. map<int, int> leafCount;
  17. ////////////////////////////////////recursion/////////////////////////////////////////////////////////
  18.  
  19. /////////////////////////////////////functions///////////////////////////////////////////////////////
  20. bool isLeaf(int node) {
  21.     return adj[node].size() == 1;
  22. }
  23. void dfs(ll num){
  24.     /*if (isLeaf(num) && num != 1) return 1;*/
  25.     vis[num] = true;
  26.     int leafCnt = 0;
  27.     for (int i = 0; i < adj[num].size(); i++) {
  28.         int ch = adj[num][i];
  29.         if (!vis[ch]) {
  30.             dfs(ch);
  31.             leafCnt += leafCount[ch];
  32.         }
  33.     }
  34.     if (isLeaf(num) && num != 1) leafCnt = 1;
  35.     leafCount[num] = leafCnt;
  36. }
  37. /////////////////////////////////////////////////////////////////////////////////////////////////////
  38.  
  39. void neverland() {
  40.     int n; cin>>n;
  41.     adj.clear();
  42.     vis.clear();
  43.     leafCount.clear();
  44.     for (int i=1;i<n;i++)
  45.     {
  46.         int x,y;
  47.         cin>>x>>y;
  48.         adj[x].pb(y);
  49.         adj[y].pb(x);
  50.     }
  51.     int q; cin>>q;
  52.     dfs(1);
  53.     for (int i=0;i<q;i++)
  54.     {
  55.         int x,y;
  56.         cin>>x>>y;
  57.         ll ans =leafCount[x]*leafCount[y];
  58.         cout<<ans<<endl;
  59.     }
  60.  
  61. }
  62. int main() {
  63.     death;
  64.     long long t=1;
  65.     cin>>t;
  66.     while(t--){
  67.         neverland();
  68.     }
  69. }
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
2
5
1 2
3 4
5 3
3 2
4
3 4
5 1
4 4
1 3
3
1 2
1 3
3
1 1
2 3
3 1
stdout
copy 
2
2
1
4
4
1
2
https://ideone.com/hV9G8a
language:
C++ (gcc 8.3)
created:
13 days 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!