fork download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. #define LB 15
  7. vector<int> ed[11007],cost[11007];
  8. pair<int,int>  ed_num[11005];
  9. int posHLD[11005],ChainHead[11005]={0},height[11004],lca_q[LB][11005];//,NodeNum[10005];
  10. int ChainNum[11005],counter,subsize[11005],seg[60005],chain_ed[11005],ChainNo;
  11. int precompute(int node)
  12. {
  13.     int ans=1;
  14.     for(int i=0;i<ed[node].size();i++)
  15.     {
  16.         int x=ed[node][i];
  17.         if(lca_q[0][node]!=x)
  18.            {
  19.                lca_q[0][x]=node;
  20.                ans+=precompute(x);
  21.            }
  22.     }
  23.     subsize[node]=ans;
  24.     return ans;
  25. }
  26.  
  27. void HLD_init(int node,int h,int costs)
  28. {
  29.    int special_child=0,mx=0,mxi=0,mxii;
  30.    height[node]=h;
  31.    if(!ChainHead[ChainNo])
  32.        {
  33.            ChainHead[ChainNo]=node;
  34.            //counter=1;
  35.        }
  36.    posHLD[node]=counter;
  37.    //NodeNum[counter]=node;
  38.    //chain_size[ChainNo]=counter;
  39.    chain_ed[counter]=costs;//Child side of the edge keeps the cost of the edge
  40.    counter++;
  41.    //cout<<counter<<"\n";
  42.    ChainNum[node]=ChainNo;
  43.  
  44.    for(int i=0;i<ed[node].size();i++)
  45.    {
  46.        int x=ed[node][i];
  47.        if(lca_q[0][node]!=x)
  48.        {
  49.            if(mx<subsize[x])
  50.            {
  51.                mx=subsize[x];
  52.                mxi=x;
  53.                mxii=i;
  54.            }
  55.        }
  56.    }
  57.    special_child=mxi;
  58.    if(special_child)
  59.       HLD_init(special_child,h+1,cost[node][mxii]);
  60.  
  61.    for(int i=0;i<ed[node].size();i++)
  62.    {
  63.        int x=ed[node][i];
  64.        if(lca_q[0][node]!=x&&x!=special_child)
  65.        {
  66.            ChainNo++;
  67.            //connector[chain][(*ch)]=connector[(*ch)][chain]=cost[node][i];
  68.            HLD_init(x,h+1,cost[node][i]);
  69.        }
  70.    }
  71.    return;
  72.  
  73. }
  74. int lca_tree(int a,int b)
  75. {
  76.     int ha,hb,diff;
  77.     if(a==b)
  78.         return a;
  79.     if(height[a]>height[b])
  80.     {
  81.         a=a^b;
  82.         b=a^b;
  83.         a=a^b;
  84.     }
  85.     ha=height[a],b=height[b];
  86.     diff=hb-ha;
  87.     for(int i=0;i<LB;i++)
  88.         if((diff>>i)&1)
  89.           a=lca_q[i][a];
  90.     if(a==b)return a;
  91.     for(int i=LB-1;i>=0;i--)
  92.         if(lca_q[i][a]!=lca_q[i][b])
  93.        {
  94.          a=lca_q[i][a];
  95.          b=lca_q[i][b];
  96.        }
  97.     return lca_q[0][a];
  98. }
  99. void build_chain(int node,int l,int r)
  100. {
  101.     if(l==r)
  102.     {
  103.         seg[node]=chain_ed[r];
  104.         return;
  105.     }
  106.     int mid=(l+r)>>1,child=node<<1;//,n1=NodeNum[mid],n2=NodeNum[mid+1];
  107.     build_chain(child,l,mid);
  108.     build_chain(child+1,mid+1,r);
  109.     seg[node]=max(seg[child],seg[child+1]);
  110.  
  111.     //seg[chain][node]=max(seg[chain][node],chain_ed[chain][mid]);
  112.     //cout<<l<<" "<<r<<"\n";
  113.     //cout<<seg[node]<<"\n";
  114.  
  115.      return;
  116. }
  117. int query(int node,int l,int r,int ql,int qr)
  118. {
  119.  
  120.     if(ql<=l&&r<=qr)
  121.     {
  122.         return seg[node];
  123.     }
  124.     int mid=(l+r)>>1,child=node<<1,ans=0;//,n1=NodeNum[mid],n2=NodeNum[mid+1];
  125.     if(mid>=ql) ans=query(child,l,mid,ql,qr);
  126.     if(mid+1<=qr) ans=max(ans,query(child+1,mid+1,r,ql,qr));
  127.     //if(mid>=ql&&mid+1<=qr)
  128.         //ans=max(ans,chain_ed[chain][mid]);
  129.     return ans;
  130. }
  131. void update(int node,int l,int r,int a,int val)
  132. {
  133.     //if((l==a&&l==r)||(l==b&&l==r))
  134.       //return;
  135.     //if(l)
  136.     //cout<<l<<" "<<r<<"\n";
  137.     //getchar();
  138.     if(l==r)
  139.     {
  140.         if(l==a)
  141.         {
  142.             chain_ed[l]=val;
  143.             seg[node]=val;
  144.         }
  145.         return ;
  146.     }
  147.     int mid=(l+r)>>1,child=node<<1,flag=0;
  148.     if(mid>=a) {
  149.             update(child,l,mid,a,val);
  150.             //flag++;
  151.     }
  152.     if(mid+1<=a) {
  153.             update(child+1,mid+1,r,a,val);
  154.             //flag++;
  155.     }
  156.     seg[node]=max(seg[child],seg[child+1]);
  157.     //if(flag==2)
  158.     //{
  159.         //chain_ed[chain][mid]=val;
  160.         //seg[chain][node]=max(seg[chain][node],val);
  161.         //return;
  162.     //}
  163.     return;
  164. }
  165. int sub_query(int u,int v)
  166. {
  167.     int uchain=ChainNum[u],vchain=ChainNum[v],mx=0;
  168.     while(1)
  169.     {
  170.         //cout<<posHLD[u]<<" "<<posHLD[v]<<"\n";
  171.         if(uchain==vchain)
  172.         {
  173.           int ans=0;
  174.           if(u!=v)
  175.             ans=query(1,1,counter-1,posHLD[v]+1,posHLD[u]);
  176.           mx=max(mx,ans);
  177.           break;
  178.         }
  179.         int ans=query(1,1,counter-1,posHLD[ChainHead[uchain]],posHLD[u]);
  180.         if(ans>mx)
  181.             mx=ans;
  182.         u=ChainHead[uchain];
  183.         u=lca_q[0][u];
  184.  
  185.         //mx=max(mx,connector[uchain][u]);
  186.         uchain=ChainNum[u];
  187.     }
  188.     return mx;
  189. }
  190. //LCA calculation remaining
  191. int HLD_query(int a,int b)
  192. {
  193.   int lca=lca_tree(a,b);
  194.   //cout<<lca<<"Sub Query\n";
  195.   return max(sub_query(a,lca),sub_query(b,lca));
  196. }
  197. int up_use(int val,int num)
  198. {
  199.     int a=ed_num[num].first,b=ed_num[num].second;
  200.     if(a==lca_q[0][b])
  201.       update(1,1,counter-1,posHLD[b],val);
  202.     else update(1,1,counter-1,posHLD[a],val);
  203.  
  204.  
  205. }
  206. int main()
  207. {
  208.  int t;
  209.  scanf("%d\n",&t);
  210.  while(t--)
  211.  {
  212.      int n;
  213.      //getchar();
  214.      scanf("%d",&n);
  215.      counter=1,ChainNo=1;
  216.      for(int i=1;i<n;i++)
  217.      {
  218.          ed[i].clear();
  219.          cost[i].clear();
  220.          ChainHead[i]=0;
  221.          for(int j=0;j<LB;j++)
  222.             lca_q[j][i]=0;
  223.      }
  224.      for(int i=1;i<n;i++)
  225.      {
  226.          int a,b,c;
  227.          scanf("%d %d %d",&a,&b,&c);
  228.          ed_num[i]=make_pair(a,b);
  229.          ed[a].push_back(b);
  230.          ed[b].push_back(a);
  231.          cost[a].push_back(c);
  232.          cost[b].push_back(c);
  233.      }
  234.      precompute(1);
  235.  
  236.      HLD_init(1,1,0);
  237.      //cout<<counter<<"\n";
  238.      build_chain(1,1,counter-1);
  239.      for(int i=1;i<LB;i++)
  240.      {
  241.          for(int j=2;j<=n;j++)
  242.          {
  243.              lca_q[i][j]=lca_q[i-1][lca_q[i-1][j]];
  244.          }
  245.      }
  246.      while(1)
  247.      {
  248.          //fflush(stdin);
  249.          char str[100];
  250.          int a,b;
  251.          scanf("%s",str);
  252.          if(str[0]=='D')
  253.             break;
  254.          scanf("%d %d",&a,&b);
  255.          //cout<<str<<" "<<a<<" "<<b<<"\n";
  256.          if(str[0]=='Q')
  257.             {
  258.                 a=HLD_query(a,b);
  259.                 printf("%d\n",a);
  260.             }
  261.         if(str[0]=='C')
  262.             {
  263.                 //if(ChainNum[a]==ChainNum[b])
  264.                 up_use(b,a);
  265.             }
  266.  
  267.      }
  268.  }
  269. }
  270.  
Time limit exceeded #stdin #stdout 5s 4824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/foVgD4
language:
C++ (gcc 8.3)
created:
9 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!