fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. //#include <ext/pb_ds/assoc_container.hpp> // Common file
  4. //#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  5. //using namespace __gnu_pbds; //  order of key(keys strictly less than)  // find_by_order
  6. //typedef tree<long long,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  7. //typedef tree<long long, null_type, less_equal<>, rb_tree_tag, tree_order_statistics_node_update> indexed_multiset;
  8.  
  9. //IF WA CHECK FOR : -
  10. // 1 > EDGE CASES LIKE N=1 , N=0
  11. // 2 > SIGNED INTEGER OVERFLOW IN MOD
  12. // 3 > CHECK THE CODE FOR LOGICAL ERRORS AND SEG FAULTS
  13. // 4 > READ THE PS ONCE AGAIN , if having double diff less than 1e-8 is same.
  14. // 5 > You Have got AC .
  15. #define ll long long
  16. #define inf (long long)(2e18)
  17. #define ff first
  18. #define ss second
  19. #define f(i,a,b) for(ll i=a;(i)<long(b);(i)++)
  20. #define fr(i,a,b) for(ll i=a;(i)>=(long long)(b);(i)--)
  21. #define it(b)  for(auto &it:(b))
  22. #define NUM  998244353
  23. #define ff first
  24. #define ss second
  25. #define pb push_back
  26. #define mp make_pair
  27. typedef vector<ll> vll;
  28. typedef pair<ll,ll> pll;
  29. long long binpow(long long a, long long b) {
  30.     if (b == 0)
  31.         return 1;
  32.     long long res = binpow(a, b / 2)%NUM;
  33.     if (b % 2)
  34.         return (((res * res)%NUM)* a)%NUM;
  35.     else
  36.         return (res * res)%NUM;
  37. }
  38. void read(vll &arr,ll n) {
  39.     if (arr.size() != n) { arr.assign(n, 0); }for (int i = 0; i < n; i++)cin >> arr[i];
  40. }
  41. inline ll min(ll a,ll b)
  42. {
  43.     if(a>b)return b;return a;
  44. }
  45. inline ll max(ll a, ll b)
  46. {
  47.     if(a>b)return a;return b;
  48. }
  49. inline ll dif(ll a,ll b)
  50. {
  51.     if(a>b)return a-b;return b-a;
  52. }
  53. long long gcd(long long a,long long b)
  54. {
  55.     if(b==0)return a;return gcd(b,a%b);
  56. }
  57. long long lcm(long long a,long long b)
  58. {
  59.     long long k=gcd(a,b);return (a*b)/k;
  60. }
  61. vector<ll> in;
  62. vector<ll> out;
  63. vector<vll> adj;
  64. vector<ll> lev;
  65. int tim = 1;
  66. void dfs(int start, int par, ll level = 1)
  67. {
  68.     in[start] = tim++;
  69.     lev[start] = level;
  70.     it(adj[start])
  71.     {
  72.         if (it != par)
  73.             dfs(it, start, level + 1);
  74.     }
  75.     out[start] = tim++;
  76. }
  77. struct segtree
  78. {
  79.     vector<pll> sum;
  80.     ll siz;
  81.     segtree(ll num)
  82.     {
  83.         siz = num;
  84.         sum.resize(4 * num + 10, mp(inf, inf));
  85.     }
  86.     void update(ll lx, ll rx, ll ind, ll level, ll node_number, ll x)
  87.     {
  88.         if (lx + 1 == rx)
  89.         {
  90.             sum[x].ff = level;
  91.             sum[x].ss = node_number;
  92.             return;
  93.         }
  94.         ll mid = (lx + rx) / 2;
  95.         if (ind < mid)
  96.         {
  97.             update(lx, mid, ind, level, node_number, 2 * x + 1);
  98.         }
  99.         else
  100.         {
  101.             update(mid, rx, ind, level, node_number, 2 * x + 2);
  102.         }
  103.         sum[x].ff = min(sum[2 * x + 1].ff, sum[2 * x + 2].ff);
  104.         sum[x].ss = sum[2 * x + 2].ss;
  105.         if (sum[x].ff == sum[2 * x + 1].ff)
  106.         {
  107.             sum[x].ss = sum[2 * x + 1].ss;
  108.         }
  109.         if (sum[2 * x + 1].ff == sum[x * 2 + 2].ff)
  110.         {
  111.             sum[x].ss = min(sum[2 * x + 1].ss, sum[x * 2 + 2].ss);
  112.         }
  113.     }
  114.     void update(ll ind, ll level, ll node_number)
  115.     {
  116.         update(0, siz, ind, level, node_number, 0);
  117.     }
  118.     pll find_min(ll lx, ll rx, ll l, ll r, ll x)
  119.     {
  120.         if (lx >= l && rx <= r)
  121.         {
  122.             return sum[x];
  123.         }
  124.         if (lx >= r || l >= rx)
  125.         {
  126.             return {inf, inf};
  127.         }
  128.         ll mid = (lx + rx) / 2;
  129.         pll l1 = find_min(lx, mid, l, r, 2 * x + 1);
  130.         pll r1 = find_min(mid, rx, l, r, 2 * x + 2);
  131.         if (l1.ff < r1.ff)
  132.         {
  133.             return l1;
  134.         }
  135.         if (l1.ff > r1.ff)
  136.         {
  137.             return r1;
  138.         }
  139.         if (l1.ss == min(l1.ss, r1.ss))
  140.         {
  141.             return l1;
  142.         }
  143.         return r1;
  144.     }
  145.     ll find_min(ll l, ll r)
  146.     {
  147.         return find_min(0, siz, l, r, 0).ss;
  148.     }
  149. };
  150. #define endl "\n"
  151. void solve(){
  152.     int n;
  153.     cin >> n;adj.clear();in.clear();
  154.     adj.resize(n + 1);
  155.     in.resize(n + 1);
  156.     out = in;
  157.     tim = 1;
  158.     lev = out;
  159.     f(i, 0, n - 1)
  160.     {
  161.         ll a, b;
  162.         cin >> a >> b;
  163.         adj[a].pb(b);
  164.         adj[b].pb(a);
  165.     }
  166.     dfs(1, 1);
  167.     // make it in out
  168.     int q;
  169.     cin >> q;
  170.     segtree tree(out[1] + 10);
  171.     vll visited(n+1);
  172.     while (q--)
  173.     {
  174.         ll a;
  175.         cin >> a;
  176.         if(visited[a]){
  177.             cout<<"YES "<<a<<endl;continue;
  178.         }
  179.         visited[a]=1;
  180.         ll res = tree.find_min(in[a] + 1, out[a]);
  181.         tree.update(in[a], lev[a], a);
  182.         if (res == inf)
  183.         {
  184.             cout << "NO" << endl;
  185.             continue;
  186.         }
  187.         else
  188.         {
  189.             cout << "YES " << res << endl;
  190.         }
  191.     }
  192. }
  193. int main()
  194. {
  195.     ios_base::sync_with_stdio(false);
  196.     cin.tie(NULL);
  197.     cout << fixed << showpoint;
  198.     cout << setprecision(12);
  199.     long long test_m=1;
  200.     cin>>test_m;int kickstart=1;
  201.     //WE WILL WIN.
  202.     while(test_m--) {
  203.         //cout<<"Case #"<<kickstart++<<": ";
  204.         solve();
  205.     }
  206. }
Runtime error #stdin #stdout 0.59s 2095880KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cqxAOz
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!