SHARE
TWEET

Untitled

a guest Jan 12th, 2017 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. Node getMax(int a, int b, int add){
  3.   Node ret = LOS;
  4.   while(dad[a] != dad[b]){
  5.     if(depth[dad[a]] > depth[dad[b]]) swap(a, b);
  6.     ret = kombaj(ret, query(1, 0, timer - 1, pos[dad[b]], pos[b]));
  7.     b = parent[dad[b]];
  8.   }
  9.   if(depth[a] > depth[b]) swap(a, b);
  10.   ret = kombaj(ret, query(1, 0, timer - 1, pos[a] + add, pos[b]));
  11.   return ret;
  12. }
  13.  
  14. void upd(int a, int b, int x){
  15.   while(dad[a] != dad[b]){
  16.     if(depth[dad[a]] > depth[dad[b]]) swap(a, b);
  17.     update(1, 0, timer - 1, pos[dad[b]], pos[b], x);
  18.     b = parent[dad[b]];
  19.   }
  20.   if(depth[a] > depth[b]) swap(a, b);
  21.   update(1, 0, timer - 1, pos[a], pos[b], x);
  22. }
  23.  
  24.   while(q--){
  25.     int t, a, b; scanf("%d %d %d", &t, &a, &b);
  26.     int lca = getLca(a, b);
  27.     if(t == 1){
  28.       Node lef = getMax(lca, a, 0);
  29.       Node rig = getMax(lca, b, 1);
  30.       ll sol = kombaj(lef, rig).best;
  31.       printf("%lld\n", sol);
  32.     }
  33.     else{
  34.       int x; scanf("%d", &x);
  35.       upd(a, b, x);
  36.     }
  37.   }
RAW Paste Data
Top