Advertisement
Infinite_S

Untitled

Jul 15th, 2018
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.36 KB | None | 0 0
  1. //In the name of ALLAH
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef vector<int> vi;
  8. typedef vector<ll> vl;
  9. typedef vector<vi> vvi;
  10. typedef vector<vl> vvl;
  11. typedef pair<int,int> pii;
  12. typedef pair<double, double> pdd;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<pii> vii;
  15. typedef vector<pll> vll;
  16. typedef double dl;
  17.  
  18. #define PB push_back
  19. //#define PB emplace_back
  20. #define F first
  21. #define S second
  22. #define MP make_pair
  23. #define endl '\n'
  24. #define all(a) (a).begin(),(a).end()
  25. #define sz(x) (int)x.size()
  26. #define mid(l,r) ((r+l)/2)
  27. #define left(node) (node*2)
  28. #define right(node) (node*2+1)
  29. #define mx_int_prime 999999937
  30.  
  31. const double PI = acos(-1);
  32. const double eps = 1e-9;
  33. const int inf = 2000000000;
  34. const ll infLL = 9000000000000000000;
  35. #define MOD 1000000007
  36. //#define harmonic(n) 0.57721566490153286l+log(n)
  37.  
  38. #define mem(a,b) memset(a, b, sizeof(a) )
  39. #define gcd(a,b) __gcd(a,b)
  40. #define sqr(a) ((a) * (a))
  41.  
  42. #define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  43. #define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
  44. #define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  45.  
  46. typedef vector<int>::iterator vit;
  47. typedef set<int>::iterator sit;
  48.  
  49. inline bool checkBit(ll n, int i) { return n&(1LL<<i); }
  50. inline ll setBit(ll n, int i) { return n|(1LL<<i); }
  51. inline ll resetBit(ll n, int i) { return n&(~(1LL<<i)); }
  52.  
  53. struct edge {
  54. int u, v, w;
  55. };
  56.  
  57. bool cmp ( const edge &a, const edge &b )
  58. {
  59. return a.w < b.w;
  60. }
  61.  
  62. string to_s(int t)
  63. {
  64. stringstream ss;
  65. ss << t;
  66. return ss.str();
  67. }
  68.  
  69.  
  70. int dx[] = {0, 0, +1, -1};
  71. int dy[] = {+1, -1, 0, 0};
  72. //int dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
  73. //int dy[] = {0, +1, 0, -1, +1, -1, +1, -1};
  74.  
  75. inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
  76. inline bool isLeapYear(ll year) { return (year%400==0) || (year%4==0 && year%100!=0); }
  77. inline ll lcm ( ll a, ll b ) { return ( a * ( b / gcd (a, b) ) ); }
  78. inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
  79. inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
  80. inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
  81. inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
  82. inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
  83. inline ll modInverse(ll a) { return modPow(a, MOD-2); }
  84. inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
  85.  
  86. /*
  87. bool seive[1010000];
  88. vi prime;
  89.  
  90. void seiveGen(int limit) {
  91. limit += 100;
  92. int sqrtn = sqrt(limit);
  93. for(int i = 3; i <= sqrtn; i += 2) {
  94. if(!seive[i>>1]) {
  95. for(int j = i * i; j < limit; j += i + i) {
  96. seive[j>>1] = 1;
  97. }
  98. }
  99. }
  100. prime.PB(2);
  101. for(int i = 3; i < limit; i += 2) {
  102. if(!seive[i>>1]) prime.PB(i);
  103. }
  104. }
  105. */
  106.  
  107. //
  108. //debug
  109. //#ifdef
  110. template < typename F, typename S >
  111. ostream& operator << ( ostream& os, const pair< F, S > & p ) {
  112. return os << "(" << p.first << ", " << p.second << ")";
  113. }
  114.  
  115. template < typename T >
  116. ostream &operator << ( ostream & os, const vector< T > &v ) {
  117. os << "{";
  118. for(auto it = v.begin(); it != v.end(); ++it) {
  119. if( it != v.begin() ) os << ", ";
  120. os << *it;
  121. }
  122. return os << "}";
  123. }
  124.  
  125. template < typename T >
  126. ostream &operator << ( ostream & os, const set< T > &v ) {
  127. os << "[";
  128. for(auto it = v.begin(); it != v.end(); ++it) {
  129. if( it != v.begin() ) os << ", ";
  130. os << *it;
  131. }
  132. return os << "]";
  133. }
  134.  
  135. template < typename T >
  136. ostream &operator << ( ostream & os, const multiset< T > &v ) {
  137. os << "[";
  138. for(auto it = v.begin(); it != v.end(); ++it) {
  139. if( it != v.begin() ) os << ", ";
  140. os << *it;
  141. }
  142. return os << "]";
  143. }
  144.  
  145. template < typename F, typename S >
  146. ostream &operator << ( ostream & os, const map< F, S > &v ) {
  147. os << "[";
  148. for(auto it = v.begin(); it != v.end(); ++it) {
  149. if( it != v.begin() ) os << ", ";
  150. os << it -> first << " = " << it -> second ;
  151. }
  152. return os << "]";
  153. }
  154.  
  155. #define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
  156.  
  157. clock_t tStart = clock();
  158. #define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
  159.  
  160. void faltu () {
  161. cerr << endl;
  162. }
  163.  
  164. template <typename T>
  165. void faltu( T a[], int n ) {
  166. for(int i = 0; i < n; ++i) cerr << a[i] << ' ';
  167. cerr << endl;
  168. }
  169.  
  170. template <typename T, typename ... hello>
  171. void faltu( T arg, const hello &... rest) {
  172. cerr << arg << ' ';
  173. faltu(rest...);
  174. }
  175. //#else
  176. //#define dbg(args...)
  177.  
  178. const int mx = 1e5+123;
  179.  
  180. struct info {
  181. int MX, MN;
  182. }t[mx*3];
  183.  
  184. int p[mx][30], chainHead[mx], chainInd[mx], chainNo, ptr, basePos[mx],baseArry[mx], parent[mx], level[mx], n, sz[mx];
  185. vii Aj[mx];
  186.  
  187. void init ( int id, int b, int e )
  188. {
  189. if ( b == e ) {
  190. t[id].MN = t[id].MX = baseArry[b];
  191. return;
  192. }
  193.  
  194. int mid = ( b + e ) >> 1;
  195.  
  196. init ( id*2, b, mid );
  197. init ( id*2+1, mid+1, e );
  198.  
  199. t[id].MN = min ( t[id*2].MN, t[id*2+1].MN );
  200. t[id].MX = max ( t[id*2].MX, t[id*2+1].MX );
  201. }
  202.  
  203. info ask ( int id, int b, int e, int i, int j )
  204. {
  205. info ret;
  206. ret.MN = 1, ret.MX = -1;
  207. if ( b > j || e < i ) return ret;
  208. if ( b >= i && e <= j ) return t[id];
  209.  
  210. int mid = ( b + e ) >> 1;
  211.  
  212. info ret1 = ask ( id*2, b, mid, i, j );
  213. info ret2 = ask ( id*2+1, mid+1, e, i, j );
  214.  
  215. ret.MN = min ( ret1.MN, ret2.MN );
  216. ret.MX = max ( ret1.MX, ret2.MX );
  217. return ret;
  218. }
  219.  
  220. int dfs ( int u, int lev )
  221. {
  222. level[u] = lev;
  223. sz[u] = 1;
  224. for ( int i = 0; i < sz (Aj[u]); i ++ ) {
  225. pii v = Aj[u][i];
  226. if ( parent[u] != v.F ) {
  227. parent[v.F] = u;
  228. sz[u] += dfs ( v.F, lev+1 );
  229. }
  230. }
  231.  
  232. return sz[u];
  233. }
  234.  
  235. void preprocess()
  236. {
  237. for ( int i = 1; i <= n; i++ ) p[i][0] = parent[i];
  238.  
  239. for ( int j = 1; ( 1 << j ) <= n; j++ ) {
  240. for ( int i = 1; i <= n; i++ ) {
  241. if ( p[i][j-1] != -1 ) p[i][j] = p[p[i][j-1]][j-1];
  242. }
  243. }
  244. }
  245.  
  246.  
  247. int LCA ( int u, int v )
  248. {
  249. if ( level[u] < level[v] ) swap ( u, v );
  250.  
  251. int dist = level[u] - level[v];
  252. while ( dist > 0 ) {
  253. int rise = log2 ( dist );
  254. u = p[u][rise];
  255. dist -= ( 1 << rise );
  256. }
  257.  
  258. if ( u == v ) return u;
  259.  
  260. for ( int i = 20; i >= 0; i-- ) {
  261. if ( p[u][i] != p[v][i] && p[u][i] != -1 ) {
  262. u = p[u][i];
  263. v = p[v][i];
  264. }
  265. }
  266.  
  267. return parent[u];
  268. }
  269.  
  270. void HLD ( int u, int cost )
  271. {
  272. if ( chainHead[chainNo] == -1 ) {
  273. chainHead[chainNo] = u;
  274. }
  275.  
  276. chainInd[u] = chainNo;
  277. basePos[u] = ++ptr;
  278. baseArry[ptr] = cost;
  279.  
  280. int m = -1, id = -1, c = -1;
  281.  
  282. for ( auto v : Aj[u] ) {
  283. if ( sz[v.F] > m && v.F != parent[u] ) {
  284. m = sz[v.F], id = v.F, c = v.S;
  285. }
  286. }
  287.  
  288. if ( id != -1 ) HLD ( id, c );
  289.  
  290. for ( auto v : Aj[u] ) {
  291. if ( parent[u] != v.F && v.F != id ) {
  292. chainNo++;
  293. HLD ( v.F, v.S );
  294. }
  295. }
  296. }
  297.  
  298. info query_up ( int u, int v, int c )
  299. {
  300. info ret;
  301. ret.MN = 1, ret.MX = -1;
  302. int chainU, chainV = chainInd[v], ans = 0;
  303. if ( v == u ) {
  304. ret.MX = ret.MN = c;
  305. return ret;
  306. }
  307.  
  308. while ( 1 ) {
  309. chainU = chainInd[u];
  310. if ( chainU == chainV ) {
  311. if ( u == v ) return ret;
  312. info ret1 = ask ( 1, 1, ptr, basePos[v]+1, basePos[u] );
  313. ret.MN = min ( ret.MN, ret1.MN );
  314. ret.MX = max ( ret.MX, ret1.MX );
  315. return ret;
  316. }
  317.  
  318. info ret1 = ask ( 1, 1, ptr, basePos[chainHead[chainU]], basePos[u] );
  319. ret.MN = min ( ret.MN, ret1.MN );
  320. ret.MX = max ( ret.MX, ret1.MX );
  321. u = chainHead[chainU];
  322. u = parent[u];
  323. }
  324.  
  325. }
  326.  
  327. bool query ( int u, int v )
  328. {
  329. int lca = LCA ( u, v );
  330. info ret1 = query_up( u, lca, -1 );
  331. info ret2 = query_up( v, lca, 1 );
  332. return ( ret1.MX == ret1.MN && ret1.MN == -1 && ret2.MN == 1 && ret2.MN == ret2.MX );
  333. }
  334.  
  335. int main()
  336. {
  337. optimize();
  338.  
  339. mem ( p, -1 );
  340. mem ( chainHead, -1 );
  341. ptr = 0, chainNo = 1;
  342.  
  343. int u, v;
  344. cin >> n;
  345. for ( int i = 1; i < n; i++ ) {
  346. cin >> u >> v;
  347. Aj[u].PB ( { v, 1 } );
  348. Aj[v].PB ( { u, -1 } );
  349. }
  350.  
  351. dfs ( 1, 0 );
  352. preprocess();
  353. HLD ( 1, -1 );
  354. init ( 1, 1, ptr );
  355. int q;
  356. cin >> q;
  357. while ( q-- ) {
  358. cin >> u >> v;
  359. if ( query( u, v ) ) cout << "Yes\n";
  360. else cout << "No\n";
  361. }
  362.  
  363. return 0;
  364. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement