fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. vector<ll>v[200005];
  5. ll dp[200005][21];
  6. ll lv,tmr;
  7. ll lazy[800005],dep[200005],in[200005],out[200005];
  8. ll csf,cc;
  9. ll seg[800005];
  10. void build(ll si,ll st,ll en)
  11. {
  12.     if(st==en)
  13.     {
  14.         seg[si]=1;
  15.         return;
  16.     }
  17.     ll mi=(st+en)/2;
  18.     build(2*si+1,st,mi);
  19.     build(2*si+2,mi+1,en);
  20.     seg[si]=1;
  21. }
  22. void upd(ll si,ll st,ll en,ll l,ll r,ll v)
  23. {
  24.     if(lazy[si])
  25.     {
  26.         seg[si]=lazy[si];
  27.         if(st!=en)
  28.         {
  29.             lazy[2*si+1]=lazy[2*si+2]=lazy[si];
  30.         }
  31.         lazy[si]=0;
  32.     }
  33.     if(st>r || en<l) return;
  34.     if(l<=st && r>=en)
  35.     {
  36.         seg[si]=v;
  37.         if(st!=en)
  38.         {
  39.             lazy[2*si+1]=lazy[2*si+2]=v;
  40.         }
  41.         return;
  42.     }
  43.     ll mi=(st+en)/2;
  44.     upd(2*si+1,st,mi,l,r,v);
  45.     upd(2*si+2,mi+1,en,l,r,v);
  46. }
  47. ll go(ll si,ll st,ll en,ll id)
  48. {
  49.     if(lazy[si])
  50.     {
  51.         seg[si]=lazy[si];
  52.         if(st!=en)
  53.         {
  54.             lazy[2*si+1]=lazy[2*si+2]=lazy[si];
  55.         }
  56.         lazy[si]=0;
  57.     }
  58.     if(st==en) { return seg[si];}
  59.     ll mi=(st+en)/2;
  60.     if(id<=mi) return go(2*si+1,st,mi,id);
  61.     else  return go(2*si+2,mi+1,en,id);
  62. }
  63. void dfs(ll s,ll pa,ll d)
  64. {
  65.   dep[s]=d;
  66.   dp[s][0]=pa;
  67.   tmr+=1;
  68.   in[s]=tmr;
  69.   for(ll i=1;i<=lv;i++)
  70.   {
  71.       dp[s][i]=dp[dp[s][i-1]][i-1];
  72.   }
  73.   for(auto i:v[s])
  74.   {
  75.       if(i!=pa) dfs(i,s,d+1);
  76.   }
  77.   out[s]=tmr;
  78. }
  79. ll lca(ll p,ll q)
  80. {
  81.    if(in[p]<=in[q] && out[p]>=out[q]) return p;
  82.    if(in[q]<=in[p] && out[q]>=out[p]) return q;
  83.    for(ll i=lv;i>=0;i--)
  84.    {
  85.        ll cur=dp[p][i];
  86.        if(!(in[cur]<=in[q] && out[cur]>=out[q]))
  87.        {
  88.            p=cur;
  89.        }
  90.    }
  91.    return dp[p][0];
  92. }
  93.  
  94. int main()
  95. {
  96.     //ios_base::sync_with_stdio(0);
  97.     //cin.tie(0);
  98.     ll i,j,k,n,m,t;
  99.     cin>>n;
  100.     csf=1;
  101.     lv=log2(n)+1;
  102.     tmr=-1;
  103.     for(i=1;i<n;i++)
  104.     {
  105.         ll p,q;
  106.         cin>>p>>q;
  107.         v[p].push_back(q);
  108.         v[q].push_back(p);
  109.     }
  110.     dfs(1,1,0);
  111.     build(0,0,tmr);
  112.     cin>>t;
  113.     while(t--)
  114.     {
  115.         char c;
  116.         ll x,y;
  117.         cin>>c>>x>>y;
  118.         ll p1=go(0,0,tmr,in[x]);
  119.         ll p2=go(0,0,tmr,in[y]);
  120.         ll p3=lca(x,y);
  121.         ll p4=go(0,0,tmr,in[p3]);
  122.         if(c=='c' || c=='d')
  123.         {
  124.            if(dp[x][0]==y) swap(x,y),swap(p1,p2);
  125.            if(dp[y][0]!=x) continue;
  126.            if(c=='c')
  127.            {
  128.                if(p1==p2) continue;
  129.  
  130.                upd(0,0,tmr,in[y],out[y],p1);
  131.            }
  132.            else
  133.            {
  134.                if(p1==p2)
  135.                {
  136.  
  137.                    upd(0,0,tmr,in[y],out[y],csf+1);
  138.                    csf+=1;
  139.                }
  140.            }
  141.         }
  142.         else
  143.         {
  144.             if(!(p1==p2 && p2==p4))
  145.                 cout<<"Impossible\n";
  146.             else
  147.             {
  148.               cout<<dep[x]+dep[y]-2*dep[p3]<<"\n";
  149.             }
  150.  
  151.         }
  152.     }
  153.     return 0;
  154. }
  155.  
Success #stdin #stdout 0s 7900KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cXf4NX
language:
C++14 (clang 8.0)
created:
6 years 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!