fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. template <typename T> inline void read(T &x)
  4. {
  5.  x=0;short f=1;char c=getchar();
  6.  for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
  7.  for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
  8.  x*=f;return;
  9. }
  10. const int N=5e5+5;
  11. using PII=pair<int,int>;
  12. #define x first
  13. #define y second
  14. vector<int>g[N];
  15. int dep[N],mp[N],col[N],dfn[N];
  16. int st[N][25],idx;
  17. void dfs(int u)
  18. {
  19.  dfn[u]=++idx,st[idx][0]=u;
  20.  for(int v:g[u]) dep[v]=dep[u]+1,dfs(v),st[++idx][0]=u;
  21. }
  22. int lg[N];
  23. int chk(int x,int y){return dep[x]<dep[y]?x:y;}
  24. int lca(int x,int y)
  25. {
  26.  if(x>y) swap(x,y); 
  27.  int k=lg[y-x+1];
  28.  return chk(st[x][k],st[y-(1<<k)+1][k]);
  29. }
  30. int dis(int x,int y)
  31. {
  32.  int l=lca(dfn[x],dfn[y]);
  33.  return dep[x]+dep[y]-2*dep[l];
  34. }
  35. struct node{
  36.  int l,r; 
  37.  PII p;
  38. }tr[N*4];
  39. bool chk_in(PII a,int x){return dis(a.x,a.y)==dis(a.x,x)+dis(a.y,x);}
  40. PII merge(PII a,PII b)
  41. {
  42.  if(a.x<0||b.x<0) return {-1,-1}; 
  43.  if(chk_in(a,b.x)&&chk_in(a,b.y)) return a;
  44.  if(chk_in(b,a.x)&&chk_in(b,a.y)) return b;
  45.  if(chk_in({a.x,b.x},a.y)&&chk_in({a.x,b.x},b.y)) return {a.x,b.x};
  46.  if(chk_in({a.x,b.y},a.y)&&chk_in({a.x,b.y},b.x)) return {a.x,b.y};
  47.  if(chk_in({a.y,b.x},a.x)&&chk_in({a.y,b.x},b.y)) return {a.y,b.x};
  48.  if(chk_in({a.y,b.y},a.x)&&chk_in({a.y,b.y},b.x)) return {a.y,b.y};
  49.  return {-1,-1}; 
  50. }
  51. void pushup(int u){tr[u].p=merge(tr[u<<1].p,tr[u<<1|1].p);}
  52. void build(int u,int l,int r)
  53. {
  54.  tr[u].l=l,tr[u].r=r;
  55.  if(l==r) return tr[u].p={mp[l],mp[l]},void();
  56.  int mid=l+r>>1;
  57.  build(u<<1,l,mid),build(u<<1|1,mid+1,r);
  58.  pushup(u); 
  59. }
  60. void modify(int u,int pos,int x)
  61. {
  62.  if(tr[u].l==tr[u].r) return tr[u].p={x,x},void();
  63.  int mid=tr[u].l+tr[u].r>>1;
  64.  if(pos<=mid) modify(u<<1,pos,x);
  65.  else modify(u<<1|1,pos,x);
  66.  pushup(u);
  67. }
  68. int query(int u,PII tmp)
  69. {
  70.  if(tr[u].l==tr[u].r) return tr[u].r;
  71.  PII t=(tmp.x==0&&tmp.y==0)?tr[u<<1].p:merge(tmp,tr[u<<1].p);
  72.  if(t.x>=0) return query(u<<1|1,t);
  73.  else return query(u<<1,tmp);
  74. }
  75. int n;
  76. int deg[N];
  77. int main()
  78. {
  79.  read(n);
  80.  for(int i=1;i<=n;++i) read(col[i]),mp[++col[i]]=i;
  81.  for(int i=2,fa;i<=n;++i) read(fa),g[fa].push_back(i),++deg[i],++deg[fa];
  82.  bool flag=true;
  83.  for(int i=1;i<=n;++i) if(deg[i]>2) flag=false;
  84.  dfs(1);
  85.  lg[0]=-1;
  86.  for(int i=1;i<N;++i) lg[i]=lg[i>>1]+1; 
  87.  for(int j=1;j<=21;++j)
  88.  {
  89.   for(int i=1;i<=idx;++i)
  90.   {
  91.    st[i][j]=st[i][j-1];
  92.    if(i+(1<<j-1)<=idx) st[i][j]=chk(st[i][j],st[i+(1<<j-1)][j-1]);
  93.   }
  94.  }
  95.  build(1,1,n);
  96.  int q;read(q);
  97.  while(q--)
  98.  {
  99.   int op,x,y;
  100.   read(op);
  101.   if(op==1)
  102.   {
  103.    read(x),read(y);
  104.    if(flag) continue;
  105.    modify(1,col[x],y),modify(1,col[y],x);
  106.    swap(col[x],col[y]);
  107.   }
  108.   else if(flag) printf("%d\n",n);
  109.   else printf("%d\n",query(1,{0,0})-1);
  110.  } 
  111.  return 0;
  112. }
  113.  
  114.  
Success #stdin #stdout 0.02s 56256KB
comments (?)
stdin
copy 
5
0 4 3 2 1
1 2 1 1
2 2 2 2 2
stdout
copy 
3
3
https://ideone.com/T0d5Se
language:
C++ (gcc 8.3)
created:
19 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!