fork download
copy 
  1. /*khanghaicode da loiihunter*/
  2. /*--------------------------*/
  3. /*Ai doc cai nay la gay*/
  4. /*Whoever reads this is gay*/
  5. /*Celui qui lit ceci est gay*/
  6. /*Wer das liest, ist schwul*/
  7. /*khong code thi thoi t la mot con cho*/
  8. /*chim trong man dem nazuna cuu lay toi*/
  9. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⣀⠀⣤⣤⣤⣤⣤⣤⣄⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀
  10. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣶⠿⠟⠉⠉⠀⠉⠁⠘⢉⣉⣛⠛⣿⠻⠷⣶⣄⡀⠀⠀⠀⢀⣴⣿⣶⣶⡾⣿⡿⠟
  11. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⡾⠟⠋⠁⠀⡄⠀⠀⠀⠀⠀⢰⠈⢿⡏⠻⣿⣿⣷⣮⠉⠃⣴⣦⡾⢫⡏⠉⠉⣥⣿⣿⣶
  12. // ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡾⠃⣀⣴⣾⣷⠋⠃⠁⠀⠀⠀⠀⠀⠀⠈⠘⠀⠁⡏⠹⣿⣦⡀⠀⢙⢿⣥⣥⠶⠟⠛⠛⠉
  13. // ⠀⠀⠐⠶⢶⣖⡒⠲⠦⠤⢤⣼⡟⢻⠷⡿⠛⠁⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠀⠀⠀⢠⠈⢯⠻⣄⢠⠆⣿⣹⡷⢦⡄
  14. // ⠀⢀⣨⣿⠋⢉⣀⣀⣠⣤⣶⡟⣳⢋⡞⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣦⣧⡄⢀⠀⠀⠀⢨⣦⠈⣿⠘⣿⣉⣀⣠⣏
  15. // ⠾⠿⠻⠿⣿⣿⣿⡿⣿⠿⢹⣿⢏⣿⠁⠀⠀⠀⢠⠀⣀⣴⡟⠀⠀⠀⠀⠀⠀⡏⠃⠻⠾⠀⠀⠸⢹⠀⠘⣷⣿⣻⡟⢿⠛⢷
  16. // ⠀⠀⠀⠀⠉⠁⠀⣠⣿⣷⣿⡟⢸⡇⠀⠀⡀⣀⣼⢾⠛⡇⣷⢰⢰⢸⢸⡆⢸⠇⢠⣀⠀⢀⡀⠀⣬⠀⠀⡸⣿⡿⢷⣶⣤⣼
  17. // ⠀⠀⠀⠀⠀⠀⢀⣿⣦⢠⣿⠁⣿⠀⡄⣼⣿⡍⢿⣄⠆⠃⠋⠈⠈⠈⠀⠁⢠⣄⣾⣭⣤⣬⣥⣼⡏⠀⠀⡇⣿⡇⣿⣅⠸⠇⣇
  18. // ⠀⠀⠀⠀⠀⢠⡞⠉⢹⣸⠇⠀⣿⡄⣇⢻⣿⡳⢈⣸⣶⣖⣆⠀⠀⠀⠀⠀⠈⠚⠉⠉⠉⠙⢻⣿⡷⠀⠀⠀⢻⣷⢈⡿⠦⣤⡟
  19. // ⠀⠀⠀⠀⠀⢈⣿⣤⣤⡿⠀⠀⠙⢻⣟⠛⣥⣾⠟⠋⠁⠀⠀⠀⠀⡖⠀⠀⠀⠀⠀⠀⠂⣿⡾⠁⠀⣀⠀⠀⢸⣿⠸⣧⠐⠁⢸
  20. // ⠀⠀⠀⠀⠀⣿⡀⠙⣿⡇⠀⠀⠀⠸⣿⣷⠛⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣼⠟⠁⣀⡤⡿⠀⠀⣼⠻⠏⠉⡃⠴⣇
  21. // ⠀⠀⠀⠀⠀⣽⠿⣿⣿⠁⢀⣤⡄⠀⢻⣿⣶⡏⠀ ⠀⠀⢀⣀⣤⣤⣶⠶⠿⣛⣿⣟⣯⣶⣿⣿⣿⠃⠀⣰⡿⢛⡷⠀⠃⢀⣿
  22. // ⠀⠀⠀⠀⠀⢿⣶⣼⣿⢀⣾⣧⠀⠀⡰⣿⣿⡁⠀⠀⠀⣼⣿⣿⠏⠁⠀⠀⠀⠙⠉⠉⠉⣹⣿⢟⡟⢠⡾⢫⣴⡿⣷⣦⣴⠏⠁
  23. // ⠀⠀⠀⠀⢰⣟⣀⣻⣿⣿⣷⣿⣦⣠⣿⣿⡽⣿⣄⠀⠀⢹⣿⡃⠀⠀⠀⠀⠀⠀⠀⣀⣴⣯⣀⣾⣷⡟⣱⣟⣼⣷⣶⡸⢿⣀⣠⣤⣴⣶
  24. // ⠀⠀⠀⠀⠈⣿⠛⢻⣿⣿⠽⠿⠈⣻⡟⣿⣿⣿⡻⣿⣤⣀⠙⠿⣤⣤⡄⠀⠀⠤⠘⠙⣿⣿⣿⣿⠟⢠⣿⠟⢁⣠⣯⣿⣿⣿⣿⣿⣿⣿
  25. // ⠀⠀⠀⠀⠀⠻⣶⠾⣿⡟⣸⣏⠛⢯⣄⣸⣄⣼⡧⠛⢿⡿⠙⢶⣤⣀⠀⠀⠀⢀⣠⣾⡿⠉⡾⢿⡴⠋⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  26. // ⠀⠀⠀⠀⠀⠀⢻⣆⣨⡿⣃⣩⣿⣦⣌⡉⠻⢏⠁⠀⠀⣻⠀⠸⣿⣿⣿⣷⡾⠛⣿⠋⠀⠀⠀⠈⠇⣴⠉⣼⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  27. // ⠀⠀⠀⠀⠀⠀⠀⣻⣿⣿⣿⣿⣿⣿⣿⣿⣦⣼⠇⢷⣄⠇⡄⠀⣿⣿⣿⣿⡇⠞⠀⡄⠀⠾⠆⠀⠀⣿⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  28. // ⠀⠀⠀⠀⠀⢠⣶⣿⣿⣿⡿⠿⠻⣿⣽⣷⣿⣆⠀⠀⠙⠷⣅⠀⢿⣿⣿⣿⡅⠀⠀⡟⡜⠀⠀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  29. // ⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣷⣾⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠹⠀⠸⣿⣿⣿⣷⡀⠸⢰⠁⠀⢰⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  30. // ⠀⠀⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⡀⠀⠀⠀⠀⢰⣿⣿⣿⣿⡟⠇⠈⠀⠀⢸⣿⣿⣿⡿⠛⠉⠉⠙⠻⣿⣿⣿⣿⣿⣿
  31. // ⠀⠀⠀⠀⠀⠈⢻⣿⣿⡟⣿⣯⣼⠟⠋⠻⢿⣿⣿⣇⠀⠀⠀⡰⢠⣿⣿⣿⣿⣿⠀⢳⣀⣀⢿⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⣿
  32. #include <bits/stdc++.h>
  33. using namespace std;
  34. int n,q;
  35. vector<int>g[100001];
  36. int p[100001];
  37. int chainhead[100001];
  38. int siz[100001];
  39. int h[100001];
  40. int in[100001];
  41. int huyenanh=0;
  42. void dfs(int u){
  43.     siz[u]=1;
  44.     for(int v:g[u]){
  45.         h[v]=h[u]+1;
  46.         dfs(v);
  47.         siz[u]+=siz[v];
  48.     }
  49. }
  50. void hld(int u){
  51.     in[u]=++huyenanh;
  52.     int best=0;
  53.     for(int v:g[u]){
  54.         if(siz[v]>siz[best])best=v;
  55.     }
  56.     if(best){
  57.         chainhead[best]=chainhead[u];
  58.         hld(best);
  59.     }
  60.     for(int v:g[u]){
  61.         if(v==best)continue;
  62.         chainhead[v]=v;
  63.         hld(v);
  64.     }
  65. }
  66. int seg[400001];
  67. int ful[400001];
  68. void update(int id,int l,int r,int u,int v,int val){
  69.     if(u>r||v<l)return;
  70.     if(l>=u&&r<=v){
  71.         ful[id]+=val;
  72.         if(ful[id]==1)seg[id]=(r-l+1);
  73.         else if(!ful[id])seg[id]=seg[id*2]+seg[id*2+1];
  74.         return;
  75.     }
  76.     int mid=(l+r)/2;
  77.     update(id*2,l,mid,u,v,val);
  78.     update(id*2+1,mid+1,r,u,v,val);
  79.     if(!ful[id])seg[id]=seg[id*2]+seg[id*2+1];
  80. }
  81. int k;
  82. vector<pair<int,int>>ds;
  83. void xl(int u,int v){
  84.     while(chainhead[u]!=chainhead[v]){
  85.         if(h[chainhead[u]]<h[chainhead[v]])swap(u,v);
  86.         ds.push_back({in[chainhead[u]],in[u]});
  87.         u=p[chainhead[u]];
  88.     }
  89.     if(u==v)return;
  90.     if(h[u]>h[v])swap(u,v);
  91.     ds.push_back({in[u]+1,in[v]});
  92. }
  93. void process(){
  94.     dfs(1);
  95.     chainhead[1]=1;
  96.     hld(1);
  97.     while(q--){
  98.         cin>>k;
  99.         int res=0;
  100.         for(int u,v,i=1;i<=k;i++){
  101.             cin>>u>>v;
  102.             xl(u,v);
  103.         }
  104.         sort(ds.begin(),ds.end());
  105.         int mxx=0;
  106.         for(auto pp:ds){
  107.             if(pp.first>mxx)res+=pp.first-mxx-1;
  108.             mxx=max(mxx,pp.second);
  109.         }
  110.         res+=n-mxx;
  111.         cout<<res-1<<"\n";
  112.         ds.clear();
  113.     }
  114. }
  115. void init(){
  116.     cin>>n>>q;
  117.     for(int i=2;i<=n;i++){
  118.         cin>>p[i];
  119.         g[p[i]].push_back(i);
  120.     }
  121. }
  122. int main(){
  123.     ios_base::sync_with_stdio(0);cin.tie(0);
  124.     #define NAME "graph"
  125.     if(fopen(NAME".inp","r")){
  126.         freopen(NAME".inp","r",stdin);
  127.         freopen(NAME".out","w",stdout);
  128.     }
  129.     //clock_t begin=clock();
  130.     init();
  131.     process();
  132.     //cerr<<"\n"<<(float)(clock()-begin)/CLOCKS_PER_SEC<<"s";
  133. }
  134.  
Success #stdin #stdout 0.01s 8744KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zgNljL
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

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!