fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define mx 10005
  4. #define ll long long
  5. int n,m;
  6. int a,b,c,d,x,y;
  7. vector< int >g[mx];
  8.  
  9. int depth[mx],subsize[mx],heavy[mx];
  10. int par[mx],chain[mx],head[mx],num[mx];
  11. int tree[3*mx];
  12. int cost[mx];
  13.  
  14. void init(int pos,int lo,int hi)
  15. {
  16.     if(lo==hi)
  17.     {
  18.         tree[pos]=cost[lo];
  19.         return;
  20.     }
  21.     int mid=(lo+hi)/2;
  22.     int left=2*pos;
  23.     int right=2*pos+1;
  24.     init(left,lo,mid);
  25.     init(right,mid+1,hi);
  26.     tree[pos]=max(tree[left],tree[right]);
  27. }
  28.  
  29. void update(int pos,int lo,int hi,int l,int r,int val)
  30. {
  31.     if(lo>r||hi<l)return;
  32.     if(lo==l&&hi==r)
  33.     {
  34.         tree[pos]=val;
  35.         return;
  36.     }
  37.     int mid=(lo+hi)/2;
  38.     int left=2*pos;
  39.     int right=2*pos+1;
  40.     update(left,lo,mid,l,r,val);
  41.     update(right,mid+1,hi,l,r,val);
  42.     tree[pos]=max(tree[left],tree[right]);
  43. }
  44.  
  45.  
  46. int query(int pos,int lo,int hi,int l,int r)
  47. {
  48.     if(lo>r||hi<l)return 0;
  49.     if(lo>=l&&hi<=r)
  50.     {
  51.         return tree[pos];
  52.     }
  53.     int mid=(lo+hi)/2;
  54.     int left=2*pos;
  55.     int right=2*pos+1;
  56.     return max(query(left,lo,mid,l,r),query(right,mid+1,hi,l,r));
  57. }
  58.  
  59.  
  60. void dfs(int src)
  61. {
  62.     subsize[src]=1;
  63.     for(int i=0;i<g[src].size();i++)
  64.     {
  65.         int u=g[src][i];
  66.         if(u==par[src])continue;
  67.         par[u]=src;
  68.         depth[u]=depth[src]+1;
  69.         dfs(u);
  70.         subsize[src]+=subsize[u];
  71.         if(heavy[src]==-1||subsize[u]>subsize[heavy[src]])
  72.         {
  73.             heavy[src]=u;
  74.         }
  75.     }
  76. }
  77.  
  78. void heavydfs(int src)
  79. {
  80.     memset(par,0,sizeof(par));
  81.     memset(heavy,-1,sizeof(heavy));
  82.  
  83.     par[1]=0;
  84.     depth[1]=0;
  85.     dfs(src);
  86.     int c=0,ptr=1;
  87.     for(int i=1;i<=n;i++)
  88.     {
  89.         if(par[i]==-1|| heavy[par[i]]!=i)
  90.         {
  91.             for(int k=i;k!=-1;k=heavy[k])
  92.             {
  93.                 chain[k]=c;
  94.                 head[k]=i;
  95.                 num[k]=ptr++;
  96.             }
  97.             c++;
  98.         }
  99.     }
  100. }
  101.  
  102. int lca(int i,int j)
  103. {
  104.     while(chain[i]!=chain[j])
  105.     {
  106.         if(depth[head[i]]>depth[head[j]])
  107.         {
  108.             i=par[head[i]];
  109.         }
  110.         else j=par[head[j]];
  111.     }
  112.     return depth[i]<depth[j]?i:j;
  113. }
  114.  
  115.  
  116. int query(int a,int lca)
  117. {
  118.     int res=0;
  119.     while(chain[a]!=chain[lca])
  120.     {
  121.         res=max(res,query(1,1,n,num[head[a]],num[a]));
  122.         a=par[head[a]];
  123.     }
  124.     if(a!=lca)res=max(res,query(1,1,n,num[lca]+1,num[a]));
  125.     return res;
  126.  
  127. }
  128.  
  129. int main()
  130. {
  131.     int tst;
  132.     scanf("%d",&tst);
  133.     while(tst--)
  134.     {
  135.         scanf("%d",&n);
  136.         vector<pair<int,pair<int,int> > >edge;
  137.         for(int i=1;i<n;i++)
  138.         {
  139.             scanf("%d %d %d",&a,&b,&c);
  140.             g[a].push_back(b);
  141.             g[b].push_back(a);
  142.             edge.push_back(make_pair(c,make_pair(a,b)));
  143.         }
  144.         heavydfs(1);
  145.         for(int i=0;i<n-1;i++)
  146.         {
  147.             x=edge[i].second.first;
  148.             y=edge[i].second.second;
  149.             int v=depth[x]>depth[y]?x:y;
  150.             cost[num[v]]=edge[i].first;
  151.         }
  152.         init(1,1,n);
  153.  
  154.  
  155.         string s;
  156.         while(cin>>s)
  157.         {
  158.             if(s=="DONE")break;
  159.             scanf("%d %d",&x,&y);
  160.             if(s=="CHANGE")
  161.             {
  162.                 x--;
  163.                 edge[x].first=y;
  164.                 a=edge[x].second.first;
  165.                 b=edge[x].second.second;
  166.                 int v=depth[a]>depth[b]?a:b;
  167.                 update(1,1,n,num[v],num[v],y);
  168.  
  169.  
  170.             }
  171.             else if(s=="QUERY")
  172.             {
  173.                 int k=lca(x,y);
  174.                 printf("%d\n",max(query(x,k),query(y,k)));
  175.             }
  176.         }
  177.         for(int i=1;i<=n;i++)g[i].clear();
  178.     }
  179. }
  180.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CdiscT
language:
C++14 (gcc 8.3)
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!