Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long int
- ll n,t,u,v,a,b,s[100007][3];
- std::vector<ll> adj[100007];
- void dfs(ll cur, ll par, ll i){
- s[i][cur] = 1;
- printf("visiting %d\n", cur);
- for(ll v: adj[cur])
- if(par!=v) dfs(v, cur, i), s[i][cur]+=s[i][v];
- }
- int main(){
- std::cin >> t;
- while (t--) {
- memset(s, 0, sizeof(s));
- for(ll i = 0; i<=n; i++) adj[i].clear();
- std::cin >> n >> a >> b;
- for(ll i = 0; i<n-1; i++){
- std::cin >> u >> v;
- adj[u].push_back(v);
- adj[v].push_back(u);
- }
- dfs(a,0,0);
- for(ll i = 1; i<=n; i++){
- // printf("s[0][%lld] = %lld\n", i, s[0][i]);
- }
- printf("\n\n");
- dfs(b,0,1);
- for(ll i = 1; i<=n; i++){
- // printf("s[0][%lld] = %lld\n", i, s[1][i]);
- }
- ll res1 = (n-s[0][b])*s[0][b];
- ll res2 = (n-s[1][a])*s[1][a];
- ll res3 = s[0][b]*s[1][a];
- // printf("res1 = %lld, res2 = %lld, res3 = %lld\n", res1, res2, res3);
- std::cout << res1+res2-res3 << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement