fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define    f               first
  5. #define    s               second
  6. #define    ll              int
  7. #define    ld              long double
  8. #define    rd(a)           cin>>a
  9. #define    pt(a)           cout<<a
  10. #define    pb              push_back
  11. #define    mp              make_pair
  12. #define    cl              endl
  13. #define    ifor(i,a,b)     for(i=a;i<=b;i++)
  14. #define    dfor(i,a,b)     for(i=a;i>=b;i--)
  15. #define    pii             pair<int,int>
  16. #define    sz              10100
  17. #define    mad             1000000007
  18.  
  19. int n;
  20. vector<pair<int,int>> adj[sz+5],vden[sz+5];
  21. int anc[15][sz];
  22. int parent[sz+5],subtree[sz+5];
  23. int mainarr[sz+5];
  24. int vchain[sz+5],povinc[sz+5];
  25. int headofchain[sz+5];
  26. int level[sz+5];
  27. int tree[6*sz];
  28.  
  29. int m=0,chaino=0,den=0;
  30.  
  31. void build(int node,int s,int e) {
  32.  
  33.     if(s==e) {
  34.         tree[node]=mainarr[s];
  35.     }
  36.     else {
  37.  
  38.         int mid=(s+e)/2;
  39.  
  40.         build(2*node,s,mid);
  41.         build(2*node +1,mid+1,e);
  42.         tree[node]=max(tree[2*node],tree[2*node +1]);
  43.     }
  44. }
  45.  
  46. void update(int node,int s,int e,int idx,int val) {
  47.  
  48.     if(s==e) {
  49.         tree[node]=val;
  50.     }
  51.     else {
  52.  
  53.         int mid=(s+e)/2;
  54.  
  55.         if(s<=idx && idx<=mid) {
  56.             update(2*node,s,mid,idx,val);
  57.         }
  58.         else {
  59.             update(2*node +1,mid+1,e,idx,val);
  60.         }
  61.         tree[node]=max(tree[2*node],tree[2*node +1]);
  62.     }
  63. }
  64.  
  65. int query(int node,int s,int e,int l,int r) {
  66.  
  67.     if(r<s || e<l) return -1;
  68.  
  69.     if(s>=l  && e<=r) return tree[node];
  70.  
  71.     int mid=(s+e)/2;
  72.  
  73.     int p1=query(2*node,s,mid,l,r);
  74.     int p2=query(2*node +1,mid+1,e,l,r);
  75.  
  76.     return max(p1,p2);
  77. }
  78. void dfs1(int cur,int prev) {
  79.  
  80.     int i,j,k;
  81.     anc[0][cur]=prev;
  82.     subtree[cur]=1;
  83.     parent[cur]=prev;
  84.  
  85.     for(i=0;i<adj[cur].size();i++) {
  86.  
  87.         if(adj[cur][i].f!=prev) {
  88.  
  89.             level[adj[cur][i].f]=level[cur] +1;
  90.             dfs1(adj[cur][i].f,cur);
  91.  
  92.             subtree[cur]+=subtree[adj[cur][i].f];
  93.         }
  94.     }
  95. }
  96.  
  97. void hld1(int cur,int prev,int cost) {
  98.  
  99.     int i,j;
  100.  
  101.     if(den==0) {
  102.         headofchain[chaino]=cur;
  103.         den=1;
  104.     }
  105.     vchain[cur]=chaino;
  106.     povinc[cur]=m;
  107.     mainarr[m++]=cost;
  108.  
  109.     int mss=-1,vtx,ec;
  110.     for(i=0;i<adj[cur].size();i++) {
  111.  
  112.         if(adj[cur][i].f!=prev) {
  113.  
  114.             if(subtree[adj[cur][i].f]>mss || mss==-1) {
  115.  
  116.                 mss=subtree[adj[cur][i].f];
  117.                 vtx=adj[cur][i].f;
  118.                 ec=adj[cur][i].s;
  119.             }
  120.         }
  121.     }
  122.  
  123.     if(mss!=-1) hld1(vtx,cur,ec);
  124.     for(i=0;i<adj[cur].size();i++) {
  125.  
  126.         if(adj[cur][i].f!=prev && adj[cur][i].f!=vtx) {
  127.             den=0;
  128.             chaino++;
  129.             hld1(adj[cur][i].f,cur,adj[cur][i].s);
  130.         }
  131.     }
  132. }
  133.  
  134. void precompute() {
  135.  
  136.     int i,j;
  137.  
  138.     for(i=1;i<=14;i++) {
  139.         for(j=1;j<=n;j++) {
  140.             if(anc[i-1][j]!=-1) {
  141.                 anc[i][j]=anc[i-1][anc[i-1][j]];
  142.             }
  143.         }
  144.     }
  145. }
  146.  
  147. int lca(int x,int y) {
  148.  
  149.     int i,j,k,lg;
  150.     if(level[y]>level[x]) swap(x,y);
  151.  
  152.     for(lg=0;1<<lg<=level[x];lg++) {
  153.         lg++;
  154.     }
  155.     lg--;
  156.     for(i=lg;i>=0;i--) {
  157.  
  158.         if((level[x]-level[y])>=(1<<i)) {
  159.             x=anc[i][x];
  160.         }
  161.     }
  162.     if(x==y) return x;
  163.  
  164.     for(i=lg;i>=0;i--) {
  165.  
  166.         if(anc[i][x]!=-1 && anc[i][x]!=anc[i][y]) {
  167.             x=anc[i][x];
  168.             y=anc[i][y];
  169.         }
  170.     }
  171.     return parent[x];
  172. }
  173.  
  174. int querybreak(int u,int v) {
  175.  
  176.     if(level[v]>level[u]) swap(u,v);
  177.     int uchain=vchain[u];
  178.     int vchaino=vchain[v];
  179.     int ans=0,val,mne,mxe;
  180.  
  181.     while(1) {
  182.  
  183.         if(u==v) break;;
  184.  
  185.         uchain=vchain[u];
  186.         if(uchain==vchaino) { 
  187.  
  188.              if(level[v]>level[u]) swap(u,v);
  189.  
  190.              mne=min(povinc[v]+1,povinc[u]);
  191.              mxe=max(povinc[v]+1,povinc[u]);
  192.  
  193.              val=query(1,1,m,mne,mxe);
  194.              ans=max(ans,val);
  195.              break;
  196.         }
  197.  
  198.         mne=min(povinc[u],povinc[headofchain[uchain]]);
  199.         mxe=max(povinc[u],povinc[headofchain[uchain]]);
  200.  
  201.         val=query(1,1,m,mne,mxe);
  202.         ans=max(ans,val);
  203.         u=headofchain[uchain];
  204.         u=parent[u];
  205.     }
  206.     return ans;
  207. }
  208.  
  209. int _querybreak(int u,int v) {
  210.  
  211.     int la=lca(u,v);
  212.     if(level[v]>level[u]) swap(u,v);
  213.     int v1=querybreak(u,la);
  214.     int v2=querybreak(v,la);
  215.  
  216.     return max(v1,v2);
  217. }
  218.  
  219. int main() {
  220.  
  221.     ios_base::sync_with_stdio(0);
  222.     cin.tie(0);
  223.     cout.tie(0);
  224.  
  225.     int i,j,k;
  226.  
  227.     int t;
  228.     cin>>t;
  229.     while(t--) {
  230.  
  231.         cin>>n;
  232.         chaino=0;m=0;den=0;
  233.         for(i=0;i<=n;i++) {
  234.  
  235.             adj[i].clear();
  236.             vden[i].clear();
  237.             headofchain[i]=-1;
  238.         }
  239.         int u,v,ec;
  240.  
  241.         for(i=1;i<=(n-1);i++) {
  242.  
  243.             cin>>u>>v>>ec;
  244.             adj[u].pb(mp(v,ec));
  245.             adj[v].pb(mp(u,ec));
  246.             vden[i].pb(mp(u,v));
  247.  
  248.             for(j=1;j<=14;j++) {
  249.                 anc[j][i]=-1;
  250.             }
  251.         }
  252.         level[1]=0;
  253.         dfs1(1,0);
  254.         hld1(1,0,0);
  255.         precompute();
  256.         m=m-1;
  257.         build(1,1,m);
  258.  
  259.         int x,y;
  260.  
  261.         while(1) {
  262.  
  263.             char s[10];
  264.             cin>>s;
  265.             if(s[0]=='D') break;
  266.  
  267.             if(s[0]=='Q') {
  268.                cin>>x>>y;
  269.                cout<<_querybreak(x,y)<<"\n";
  270.             }
  271.             else {
  272.                 cin>>x>>y;
  273.                 int fn=vden[x][0].first,sn=vden[x][0].second;
  274.                 if(level[sn]>level[fn]) swap(fn,sn);
  275.                 update(1,1,m,povinc[fn],y);
  276.             }
  277.         }
  278.     }
  279.     return 0;
  280. }
Time limit exceeded #stdin #stdout 5s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/fLWfpx
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 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!