Codeforces Round 881 (Div. 3) 1843D - Apple Tree Solution

 

Problem Link :  https://codeforces.com/contest/1843/problem/D

Solution in C++:

1. /// Author : AH_Tonmoy
2. #include <bits/stdc++.h>
3. using namespace std;
4. const int mx = 2e5 + 9 ;
5. vector<int> adj[mx];
6. int cnt[mx] ;
7. void dfs( int u , int par=0) {
8. cnt[u] = 0 ;
9. for ( auto v : adj[u]){
10. if ( v == par ) continue ;
11. dfs(v,u) ;
12. cnt[u] +=cnt[v] ;
13. }
14. cnt[u] = max (cnt[u] , 1) ;
15. }
16. int32_t main() {
17. ios_base::sync_with_stdio(0);
18. cin.tie(0);
19. int t;
20. cin >> t;
21. while (t--) {
22. int n ;
23. cin >> n ;
24. for ( int i = 1 ; i <= n ; i++){
25. adj[i].clear() ;
26. }
27. for ( int i = 1 ; i < n ; i++){
28. int u , v ;
29. cin >> u >> v ;
30. adj[u].push_back(v) ;
31. adj[v].push_back(u) ;
32. }
33. int q ;
34. cin >> q ;
35. dfs(1) ;
36. while (q--) {
37. int x , y ;
38. cin >> x >> y ;
39. cout << 1ll *cnt[x] * cnt[y] << '\n' ;
40. }
41. }
42. return 0 ;
43. }