fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct muchie
  7. {
  8.     int nod,poz;
  9.     muchie(int nod1,int poz1) {nod=nod1;poz=poz1;}
  10. };
  11. vector<muchie> v[100010];
  12. vector<int> aib[100010];
  13. int niv[100010],lant1[100010],lant2[100010],poz[100010],size[100010];
  14. char vaz[100010];
  15.  
  16. void aib_update(int nr,int i,int s)
  17. {
  18.     for(;i<=size[nr];i+=i&(-i)) aib[nr][i]+=s;
  19. }
  20.  
  21. int aib_query(int nr,int i)
  22. {
  23.     int s=0;
  24.     for(;i>0;i-=i&(-i)) s+=aib[nr][i];
  25.     return s;
  26. }
  27.  
  28. int main()
  29. {
  30.     //freopen("file.in", "r", stdin);
  31.     //freopen("file.out", "w", stdout);
  32.     int n,nod,x,y,m,nr=0,tip,a,b;
  33.     scanf("%d",&n);
  34.     for(int i=1;i<n;i++)
  35.     {
  36.         scanf("%d%d",&x,&y);
  37.         v[x].push_back(muchie(y,i));
  38.         v[y].push_back(muchie(x,i));
  39.     }
  40.     for(nod=1;nod<=n;nod++) if(v[nod].size()>2) break;
  41.     if(nod==n+1) nod=1;
  42.     vaz[nod]=1;
  43.     for(vector<muchie>::iterator it=v[nod].begin();it!=v[nod].end();it++)
  44.     {
  45.         lant1[it->poz]=++nr;
  46.         poz[it->poz]=1;
  47.         int x=it->nod;
  48.         for(int i=2;;i++)
  49.         {
  50.             lant2[x]=nr;
  51.             vaz[x]=1;
  52.             niv[x]=i-1;
  53.             if(!vaz[v[x][0].nod]) {poz[v[x][0].poz]=i;lant1[v[x][0].poz]=nr;x=v[x][0].nod;}
  54.             else if(v[x].size()>1) {poz[v[x][1].poz]=i;lant1[v[x][1].poz]=nr;x=v[x][1].nod;}
  55.             else
  56.             {
  57.                 size[nr]=i;
  58.                 aib[nr].resize(size[nr]+2);
  59.                 break;
  60.             }
  61.         }
  62.     }
  63.     scanf("%d",&m);
  64.     for(int i=1;i<=m;i++)
  65.     {
  66.         scanf("%d",&tip);
  67.         if(tip==1)
  68.         {
  69.             scanf("%d",&a);
  70.             aib_update(lant1[a],poz[a],-1);
  71.         }
  72.         else if(tip==2)
  73.         {
  74.             scanf("%d",&a);
  75.             aib_update(lant1[a],poz[a],1);
  76.         }
  77.         else
  78.         {
  79.             scanf("%d%d",&a,&b);
  80.             if(lant2[a]==lant2[b])
  81.             {
  82.                 int x=niv[a],y=niv[b];
  83.                 if(x>y) swap(x,y);
  84.                 if(aib_query(lant2[a],y)-aib_query(lant2[a],x)) printf("-1\n");
  85.                 else printf("%d\n",y-x);
  86.             }
  87.             else if(a==nod || b==nod)
  88.             {
  89.                 if(a==nod) swap(a,b);
  90.                 if(a==nod) {printf("0\n");continue;}
  91.                 if(aib_query(lant2[a],niv[a])) printf("-1\n");
  92.                 else printf("%d\n",niv[a]);
  93.             }
  94.             else
  95.             {
  96.                 if(aib_query(lant2[a],niv[a])+aib_query(lant2[b],niv[b])) printf("-1\n");
  97.                 else printf("%d\n",niv[a]+niv[b]);
  98.             }
  99.         }
  100.     }
  101.     return 0;
  102. }
Success #stdin #stdout 0s 7672KB
comments (?)
stdin
copy 
7
1 5
6 4
2 3
3 5
5 6
3 7
1
3 4 2
stdout
copy 
1
https://ideone.com/W4g1PB
language:
C++14 (gcc 8.3)
created:
9 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!