fork(6) download
copy 
  1. //Shreyans Sheth [bholagabbar]
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define readFile freopen("E:/Shreyans/Documents/Coding Workspace/STDINPUT.txt","v",stdin);
  6. #define getPrecision(s,p) fixed<<setprecision(p)<<s
  7. #define boostIO ios_base::sync_with_stdio(0), cin.tie(0)
  8. #define CLR(s) memset(&s, 0, sizeof s)
  9. #define hashset unordered_set
  10. #define hashmap unordered_map
  11. #define PI(x) printf("%d", x)
  12. #define PL(x) printf("%ld", x)
  13. #define SI(x) scanf("%d", &x)
  14. #define SD(x) scanf("%lf", &x)
  15. #define SL(x) scanf("%lld", &x)
  16. #define pb push_back
  17. #define mp make_pair
  18. #define N 10001
  19. #define LN 14
  20. #define F first
  21. #define S second
  22. #define endl '\n'
  23.  
  24. typedef long long int ll;
  25. typedef long double ld;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28.  
  29. vector<int> adj[N];
  30. vector<int> edges[N];
  31. vector<int> idx[N];
  32.  
  33. int subSize[N];
  34. int depth[N];
  35.  
  36. int lca[LN][N];
  37.  
  38. int segTree[N<<2];
  39.  
  40. int pos;
  41. int chainNo;
  42. int chainHead[N];
  43. int chainIndex[N];
  44. int arr[N];
  45. int basePos[N];
  46. int endNode[N];
  47.  
  48. void Dfs(int node, int parent, int level) {
  49.     depth[node] = level;
  50.     lca[0][node] = parent;
  51.     subSize[node] = 1;
  52.     int x = adj[node].size();
  53.     while (x--) {
  54.         int next = adj[node][x];
  55.         if (next != parent){
  56.             endNode[idx[node][x]] = next;
  57.             Dfs(next, node, level+1);
  58.             subSize[node] += subSize[next];
  59.         }
  60.     }
  61. }
  62.  
  63. void HLD(int node, int cost, int parent) {
  64.     if (chainHead[chainNo] == -1) {
  65.         chainHead[chainNo] = node;
  66.     }
  67.     pos++;
  68.     chainIndex[node] = chainNo;
  69.     basePos[node] = pos;
  70.     arr[pos] = cost;
  71.     int specialChild = -1, edgeCost = 0;
  72.     int x = adj[node].size();
  73.     while (x--) {
  74.         int next = adj[node][x];
  75.         if (next != parent) {
  76.             if (specialChild == -1 || subSize[next] > subSize[specialChild]) {
  77.                 specialChild = next;
  78.                 edgeCost = edges[node][x];
  79.             }
  80.         }
  81.     }
  82.     if (specialChild != -1) {
  83.         HLD(specialChild, edgeCost, node);
  84.     }
  85.     x = adj[node].size();
  86.     while (x--) {
  87.         int next = adj[node][x];
  88.         if (next != parent && next != specialChild) {
  89.             chainNo++;
  90.             HLD(next, edges[node][x], node);
  91.         }
  92.     }
  93. }
  94.  
  95. void initializeLCA(int n) {
  96.     for (int j = 1; j < LN; j++) {
  97.         for (int i = 1; i <= n; i++) {
  98.             lca[j][i] = lca[j - 1][lca[j - 1][i]];
  99.         }
  100.     }
  101. }
  102.  
  103. int LCA(int x, int y) {
  104.     if (depth[x] < depth[y]) {
  105.         std::swap(x, y);
  106.     }
  107.     for (int i = LN - 1; i >= 0; i--) {
  108.         if (depth[x] - (1 << i) >= depth[y]) {
  109.             x = lca[i][x];
  110.         }
  111.     }
  112.     if (x == y) {
  113.         return x;
  114.     }
  115.     for (int i = LN - 1; i >= 0; i--) {
  116.         if (lca[i][x] != lca[i][y]) {
  117.             x = lca[i][x];
  118.             y = lca[i][y];
  119.         }
  120.     }
  121.     return lca[0][x];
  122. }
  123.  
  124. void buildSegTree(int node, int u, int v) {
  125.     if(u == v) {
  126.         segTree[node] = arr[u];
  127.         return ;
  128.     }
  129.     int mid = (u + v) >> 1;
  130.     int lc = node << 1;
  131.     int rc = lc | 1;
  132.     buildSegTree (lc, u, mid);
  133.     buildSegTree (rc, mid + 1, v);
  134.     segTree[node] = std::max(segTree[lc], segTree[rc]);
  135. }
  136.  
  137. void updateSegTree(int node, int u, int v, int i, int val) {
  138.     if(u == v) {
  139.         segTree[node] = val;
  140.         return;
  141.     }
  142.     int mid = (u + v) >> 1;
  143.     int lc = node << 1;
  144.     int rc= lc | 1;
  145.     if(i <= mid) {
  146.         updateSegTree(lc, u, mid, i, val);
  147.     } else {
  148.         updateSegTree(rc, mid+  1, v, i, val);
  149.     }
  150.     segTree[node]=std::max(segTree[lc], segTree[rc]);
  151. }
  152.  
  153. int querySegTree(int node, int u, int v, int ql, int qr) {
  154.     if(ql > v || u > qr) {
  155.         return 0;
  156.     }
  157.     if(u >= ql && v <= qr) {
  158.         return segTree[node];
  159.     }
  160.     int mid = (u + v) >> 1;
  161.     int lc = node << 1;
  162.     int rc = lc | 1;
  163.     int lv = querySegTree(lc, u, mid, ql, qr);
  164.     int rv = querySegTree(rc, mid + 1, v, ql, qr);
  165.     return std::max(rv,lv);
  166. }
  167.  
  168. int queryUp(int u,int v) {
  169.     if(u == v) {
  170.         return 0;
  171.     }
  172.     int lchain, rchain = chainIndex[v], ans = -1;
  173.     while (1) {
  174.         lchain = chainIndex[u];
  175.         if(lchain == rchain) {
  176.             if(u == v) {
  177.                 break;
  178.             }
  179.             int currAns = querySegTree(1, 1, pos, basePos[v] + 1, basePos[u]);
  180.             ans = std::max(ans, currAns);
  181.             break;
  182.         }
  183.         int currAns = querySegTree(1, 1, pos, basePos[chainHead[lchain]], basePos[u]);
  184.         ans = std::max(ans, currAns);
  185.         u = chainHead[lchain];
  186.         u = lca[0][u];
  187.     }
  188.     return ans;
  189. }
  190.  
  191. void Initialize(int n) {
  192.     for (int i = 0; i <= n; i++) {
  193.         adj[i].clear();
  194.         edges[i].clear();
  195.         idx[i].clear();
  196.         chainHead[i] = -1;
  197.         for (int j = 0; j < LN; j++) {
  198.             lca[j][i]=-1;
  199.         }
  200.     }
  201. }
  202.  
  203. int queryPath(int u, int v) {
  204.     int lca = LCA(u, v);
  205.     int a = queryUp(u, lca);
  206.     int b = queryUp(v, lca);
  207.     return std::max(a, b);
  208. }
  209.  
  210. void Update(int i, int val) {
  211.     int node = endNode[i];
  212.     updateSegTree(1, 1, pos, basePos[node], val);
  213. }
  214.  
  215. int main() {
  216.     int t;
  217.     SI(t);
  218.     while (t--) {
  219.         int n;
  220.         SI(n);
  221.         Initialize(n);
  222.         for (int i=1;i<n;i++) {
  223.             int u, v, w;
  224.             SI(u), SI(v), SI(w);
  225.             adj[u].pb(v);
  226.             edges[u].pb(w);
  227.             idx[u].pb(i);
  228.             adj[v].pb(u);
  229.             edges[v].pb(w);
  230.             idx[v].pb(i);
  231.         }
  232.         Dfs(1, 0, 0);
  233.         initializeLCA(n);
  234.         pos = -1;
  235.         chainNo = 1;
  236.         HLD(1, 0, 0);
  237.         buildSegTree(1, 1,pos);
  238.         char str[10];
  239.         scanf("%s", str);
  240.         while (str[0] != 'D') {
  241.             int type, u ,v;
  242.             SI(u);
  243.             SI(v);
  244.             if (str[0] == 'Q') {
  245.                 PI(queryPath(u, v));
  246.                 printf("\n");
  247.             } else {
  248.                 Update(u, v);
  249.             }
  250.             scanf("%s", str);
  251.         }
  252.     }
  253. }
Success #stdin #stdout 0s 4792KB
comments (?)
stdin
copy 
1

3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
stdout
copy 
1
3
https://ideone.com/9XpM4q
language:
C++14 (gcc 8.3)
created:
8 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!