fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll MAX=1e7;
  5. ll eindx;
  6. ll et[20005],d[20005],h[10005];
  7. list<ll>l[10005];
  8. void euler(ll s,ll p,ll dep)
  9. {
  10.     et[eindx]=s;
  11.     d[eindx]=dep;
  12.     h[s]=eindx++;
  13.     for(auto it=l[s].begin();it!=l[s].end();it++)
  14.     {
  15.         if(*it==p)
  16.         continue;
  17.         euler(*it,s,dep+1);
  18.         et[eindx]=s;
  19.         d[eindx++]=dep;
  20.     }
  21. }
  22. pair<ll,ll>seg[80005];
  23. void builds(ll s,ll e,ll p)
  24. {
  25.     if(s==e)
  26.     {
  27.         seg[p]=make_pair(d[s],s);
  28.         return;
  29.     }
  30.     ll mid=(s+e)/2;
  31.     builds(s,mid,2*p+1);
  32.     builds(mid+1,e,2*p+2);
  33.     seg[p]=seg[2*p+1].first<seg[2*p+2].first?seg[2*p+1]:seg[2*p+2];
  34. }
  35. pair<ll,ll> querrys(ll s,ll e,ll p,ll ql,ll qh)
  36. {
  37.     if(s>qh||e<ql)
  38.     return make_pair(MAX,0);
  39.     if(s>=ql&&e<=qh)
  40.     return seg[p];
  41.     ll mid=(s+e)/2;
  42.     pair<ll,ll>p1= querrys(s,mid,2*p+1,ql,qh);
  43.     pair<ll,ll>p2=querrys(mid+1,e,2*p+2,ql,qh);
  44.     pair<ll,ll>p3=p1.first<p2.first?p1:p2;
  45.     return p3;
  46. }
  47. ll getlca(ll u,ll v)
  48. {
  49.     ll u1=min(h[u],h[v]);
  50.     ll u2=max(h[u],h[v]);
  51.     return et[querrys(0,eindx-1,0,u1,u2).second];
  52. }
  53. struct node
  54. {
  55.     ll data,par,size,depth;
  56.     ll segpos,chain;
  57.     ll chainpos;
  58. }vtx[10005];
  59. ll cindx,pos,spos;
  60. ll head[1001];
  61. ll b[10005];//seg aaray for hld
  62. void dfs(ll s,ll p,ll dep)
  63. {
  64.     vtx[s].par=p;
  65.     vtx[s].depth=dep;
  66.     vtx[s].size=1;
  67.     for(auto it=l[s].begin();it!=l[s].end();it++)
  68.     {
  69.         if(*it==p)
  70.         continue;
  71.         dfs(*it,s,dep+1);
  72.         vtx[s].size+=vtx[*it].size;
  73.     }
  74. }
  75. void hld(ll s,ll p)
  76. {
  77.     if(head[cindx]==-1)
  78.     head[cindx]=s;
  79.     vtx[s].chain=cindx;
  80.     vtx[s].chainpos=pos;
  81.     vtx[s].segpos=spos;
  82.     b[spos++]=vtx[s].data;
  83.     ll special=-1,ssize=0;
  84.     for(auto it=l[s].begin();it!=l[s].end();it++)
  85.     {
  86.         if(*it==p)
  87.         continue;
  88.         if(vtx[*it].size>ssize)
  89.         {
  90.             ssize=vtx[*it].size;
  91.             special=*it;
  92.  
  93.         }
  94.     }
  95.     if(special!=-1)
  96.     {
  97.         pos++;
  98.         hld(special,s);
  99.     }
  100.     for(auto it=l[s].begin();it!=l[s].end();it++)
  101.     {
  102.         if((*it==p)||(*it==special))
  103.         continue;
  104.         pos=1;
  105.         cindx++;
  106.         hld(*it,s);
  107.     }
  108. }
  109. ll segt[40005];
  110. void build(ll s,ll e,ll p)
  111. {
  112.     if(s==e)
  113.     {
  114.         segt[p]=b[s];
  115.         return;
  116.     }
  117.     ll mid=(s+e)/2;
  118.     build(s,mid,2*p+1);
  119.     build(mid+1,e,2*p+2);
  120.     segt[p]=segt[2*p+1]+segt[2*p+2];
  121. }
  122. ll querry(ll s,ll e,ll p,ll ql,ll qh)
  123. {
  124.     if(s>e)
  125.     return 0;
  126.     if(s>qh||e<ql)
  127.     return 0;
  128.     if(s>=ql&&e<=qh)
  129.     return segt[p];
  130.     ll mid=(s+e)/2;
  131.     ll u=querry(s,mid,2*p+1,ql,qh);
  132.     ll v=querry(mid+1,e,2*p+2,ql,qh);
  133.     return u+v;
  134. }
  135. ll getans(ll u,ll v)
  136. {
  137.     ll c1,c2,sum=0;
  138.     c2=vtx[v].chain;
  139.     while(1)
  140.     {
  141.         c1=vtx[u].chain;
  142.         if(u==v)
  143.         return sum;
  144.         if(c1==c2)
  145.         {
  146.             sum+=querry(0,spos-1,0,vtx[v].segpos+1,vtx[u].segpos);
  147.             return sum;
  148.         }
  149.         ll p=head[vtx[u].chain];
  150.         if(p==u)
  151.         {
  152.             sum+=querry(0,spos-1,0,vtx[p].segpos,vtx[u].segpos);
  153.             u=vtx[p].par;
  154.         }
  155.         else{
  156.         sum+=querry(0,spos-1,0,vtx[p].segpos+1,vtx[u].segpos);
  157.         u=p;}
  158.     }
  159. }
  160. ll solve1(ll x,ll y)
  161. {
  162.     ll lca=getlca(x,y);
  163.     ll u=getans(x,lca);
  164.     ll v=getans(y,lca);
  165.     return v+u;
  166. }
  167. ll extract(ll u,ll v,ll k,ll p)
  168. {
  169.     ll count=p;
  170.     while(1)
  171.     {
  172.         ll u1=vtx[u].chainpos;
  173.         if(count-u1<=k)
  174.         {
  175.             while(count>k)
  176.             {
  177.                 count--;
  178.                 u=vtx[u].par;
  179.             }
  180.             return u;
  181.         }
  182.         else
  183.         {
  184.             count-=u1;
  185.             u=vtx[head[vtx[u].chain]].par;
  186.         }
  187.     }
  188. }
  189. ll getkth(ll x,ll y,ll k)
  190. {
  191.     ll lca=getlca(x,y);
  192.     ll u1=vtx[x].depth-vtx[lca].depth+1;
  193.     if(u1>=k)// ans lies in  subtree containing x
  194.         return extract(x,lca,u1-k+1,u1);
  195.     else//ans lies in subtree containing y
  196.     {
  197.         ll u2=vtx[y].depth-vtx[lca].depth+1;
  198.         return extract(y,lca,k-u1+1,u2);
  199.     }
  200. }
  201. struct edge
  202. {
  203.     ll vrtx,cost;
  204. };
  205. list<edge>l1[10005];
  206. void efs(ll s,ll p,ll c)
  207. {
  208.     vtx[s].data=c;
  209.     for(auto it=l1[s].begin();it!=l1[s].end();it++)
  210.     {
  211.         if(it->vrtx==p)
  212.         continue;
  213.         efs(it->vrtx,s,it->cost);
  214.     }
  215. }
  216. int main()
  217. {
  218.     ll t,n,i,x,y,z;
  219.     scanf("%lld",&t);
  220.     while(t--)
  221.     {
  222.         scanf("%lld",&n);
  223.         for(i=0;i<10005;i++){
  224.         l[i].clear();
  225.         l1[i].clear();}
  226.         for(i=1;i<n;i++)
  227.         {
  228.             scanf("%lld%lld%lld",&x,&y,&z);
  229.             x--;
  230.             y--;
  231.             l[x].push_back(y);
  232.             l[y].push_back(x);
  233.             edge k1;
  234.             k1.vrtx=y;
  235.             k1.cost=z;
  236.             l1[x].push_back(k1);
  237.             k1.vrtx=x;
  238.             l1[y].push_back(k1);
  239.         }
  240.         efs(0,-1,0);
  241.         eindx=0;
  242.         euler(0,-1,1);
  243.         for(i=0;i<80005;i++)
  244.         seg[i]=make_pair(MAX,0);
  245.         builds(0,eindx-1,0);
  246.         cindx=0;
  247.         pos=1;
  248.         spos=0;
  249.         memset(head,-1,sizeof(head));
  250.         memset(segt,0,sizeof(segt));
  251.         dfs(0,-1,1);
  252.         hld(0,-1);
  253.         build(0,spos-1,0);
  254.         char str[10];
  255.         while(1)
  256.         {
  257.             scanf("%s",str);
  258.             if(strcmp(str,"DONE")==0)
  259.             break;
  260.             if(strcmp(str,"DIST")==0)
  261.             {
  262.                 scanf("%lld%lld",&x,&y);
  263.                 x--;
  264.                 y--;
  265.                 printf("%lld\n",solve1(x,y));
  266.             }
  267.             else
  268.             {
  269.                 scanf("%lld%lld%lld",&x,&y,&z);
  270.                 x--;
  271.                 y--;
  272.                 ll u=getkth(x,y,z);
  273.                 printf("%lld\n",u+1);
  274.             }
  275.         }
  276.         printf("\n");
  277.     }
  278. }
Runtime error #stdin #stdout 0s 18296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1HCs4A
language:
C++ (gcc 8.3)
created:
4 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!