-
Notifications
You must be signed in to change notification settings - Fork 0
/
Apple_Tree.cpp
53 lines (47 loc) · 928 Bytes
/
Apple_Tree.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <bits/stdc++.h>
using namespace std;
int n,q;
vector<vector<int>> a;
vector<long long int> cnt;
void dfs(int u, int prev){
if(a[u].size()==1 && a[u][0]==prev){
cnt[u]=1;
}
else{
for(auto nxt:a[u]){
if(nxt!=prev){
dfs(nxt,u);
cnt[u]+=cnt[nxt];
}
}
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
int t;
cin>>t;
while(t--){
cin>>n;
a.assign(n, vector<int>());
cnt.assign(n,0);
for(int i=0;i<n-1;i++){
int u,v;
cin>>u>>v;
u--;
v--;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(0,-1);
cin>>q;
while(q--){
long long int x,y;
cin>>x>>y;
cout<<cnt[x-1]*cnt[y-1]<<endl;
}
}
return 0;
}