#include "garden.h" #include "gardenlib.h" #include "bits/stdc++.h" using namespace std; const int MAXN = 150000; const int MAXM = 150000; const int MAXL = 29; int Rf[MAXN]; int Rs[MAXN]; int succreal[MAXN][MAXL]; int succfake[MAXN][MAXL]; bool _second_path_real[MAXN][MAXL]; bool _second_path_fake[MAXN][MAXL]; int succ(int x, int k) { int ans = x; bool fake = false; int cur = pow(2,MAXL); int curval = MAXL; while (k!=0) { while (cur>k) cur/=2,curval--; k-=cur; if (!fake) { if (_second_path_real[ans][curval]) fake = true; ans = succreal[ans][curval]; } else { if (!_second_path_fake[ans][curval]) fake = false; ans = succfake[ans][curval]; } } return ans; } void count_routes(int n, int m, int p, int R[][2], int q, int G[]) { fill(Rf,Rf+n,-1); fill(Rs,Rs+n,-1); for (int i = 0; i<m; i++) { int x = R[i][0], y = R[i][1]; if (Rf[x] == -1) Rf[x] = y; else if (Rs[x] == -1) Rs[x] = y; if (Rf[y] == -1) Rf[y] = x; else if (Rs[y] == -1) Rs[y] = x; } for (int i = 0; i<n; i++) if (Rs[i] == -1) Rs[i] = Rf[i]; for (int j = 0; j<n; j++) { succreal[j][0] = Rf[j]; if (Rf[Rf[j]] == j) _second_path_real[j][0] = true; succfake[j][0] = Rs[j]; if (Rf[Rs[j]] == j) _second_path_fake[j][0] = true; } for (int i = 1; i<=MAXL; i++) { for (int j = 0; j<n; j++) { if (_second_path_real[j][i-1]) { succreal[j][i] = succfake[succreal[j][i-1]][i-1]; _second_path_real[j][i] = _second_path_fake[succreal[j][i-1]][i-1]; } else { succreal[j][i] = succreal[succreal[j][i-1]][i-1]; _second_path_real[j][i] = _second_path_real[succreal[j][i-1]][i-1]; } if (_second_path_fake[j][i-1]) { succfake[j][i] = succfake[succfake[j][i-1]][i-1]; _second_path_fake[j][i] = _second_path_fake[succfake[j][i-1]][i-1]; } else { succfake[j][i] = succreal[succfake[j][i-1]][i-1]; _second_path_fake[j][i] = _second_path_real[succfake[j][i-1]][i-1]; } } } for (int i = 0; i<q; i++) { int a = 0; for (int j = 0; j<n; j++) if (succ(j,G[i]) == p) a++; answer(a); } }