API tools faq
paste
Advertisement
dipBRUR

HLD

dipBRUR
Oct 4th, 2018
160
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.75 KB | None | 0 0
raw download clone embed print report
  1. #define inf                  -123456789
  2.  
  3. static const int MAXN = 1e5 + 5;
  4. static const int LOGN = 18;
  5.  
  6. int     chainNo,            // number of chain
  7.         chainHead[MAXN],    // starting node of the chain
  8.         chainInd[MAXN],     // chain no of a node
  9.         chainPos[MAXN],     // position in the chain in the chain
  10.         chainSize[MAXN],    // total no of node in the chain
  11.         baseArray[MAXN],    // create an array using all chain
  12.         posBase[MAXN],      // position of a node in baseArray
  13.         ptr,                // pointer of baseArray
  14.         depth[MAXN],        // depth of a node in dfs tree
  15.         father[MAXN][LOGN], // sparse table
  16.         subTreeSize[MAXN],  // subtree size of a node
  17.         startNode[MAXN],    // start node of an edge in dfs tree
  18.         endNode[MAXN],      // end node of an edge in dfs tree
  19.         S,                  // starting index of baseArray in Segment tree
  20.         E,                  // last index of baseArray
  21.         edgeCost[MAXN];     // cost of an edge store in a node wrt to dfs tree      
  22. struct node
  23. {
  24.     int v, e, w;  // v: child node, e: edge number, w: edge cost
  25.     node(int vv = 0, int ee = 0, int ww = 0) : v(vv), e(ee), w(ww) {}
  26. };
  27. vector <node> G[MAXN];
  28.  
  29. void DFS(int u = 1, int p = -1)
  30. {
  31.     for (int i = 1; i < LOGN; i++)
  32.         father[u][i] = father[father[u][i-1]][i-1];
  33.     subTreeSize[u] = 1;
  34.  
  35.  
  36.     for (auto &it : G[u])
  37.     {
  38.         int v = it.v;
  39.         int e = it.e;
  40.         int w = it.w;
  41.         if (v == p)
  42.             continue;
  43.         depth[v] = depth[v] + 1;
  44.         father[v][0] = u;
  45.         startNode[e] = u;
  46.         endNode[e] = v;   // use it to update an edge
  47.         edgeCost[v] = w;
  48.         DFS(v, u);
  49.         subTreeSize[u] += subTreeSize[v];
  50.     }
  51. }
  52.  
  53. int LCA(int u, int v)
  54. {
  55.     if (depth[u] < depth[v])
  56.         swap(u, v);
  57.     for (int i = LOGN-1; i >= 0; i--)
  58.     {
  59.         if (depth[father[u][i]] >= depth[v])
  60.         {
  61.             u = father[u][i];
  62.         }
  63.     }
  64.     if (u == v)
  65.         return u;
  66.     for (int i = LOGN-1; i >= 0; i--)
  67.     {
  68.         if (father[u][i] != father[v][i])
  69.         {
  70.             u = father[u][i];
  71.             v = father[v][i];
  72.         }
  73.     }
  74.     return father[u][0];
  75. }
  76.  
  77. void HLD(int u = 1, int p = -1) // nodes are numbered from 1,2,3,………… ,n
  78. {
  79.     if (chainHead[chainNo] == -1)
  80.         chainHead[chainNo] = u;
  81.     chainInd[u] = chainNo;
  82.     ptr++;
  83.     baseArray[ptr] = edgeCost[u];
  84.     posBase[u] = ptr;
  85.     int specialChild = -1;
  86.     int maxSize = -1;
  87.  
  88.  
  89.  
  90.  
  91.     for (auto &it : G[u])
  92.     {
  93.         int v = it.v;
  94.         if (v == p)
  95.             continue;
  96.         if (subTreeSize[v] > maxSize)
  97.             maxSize = subTreeSize[v], specialChild = v;
  98.     }
  99.     if (specialChild != -1)
  100.         hld(specialChild, u);
  101.     for (auto &it : G[u])
  102.     {
  103.         int v = it.v;
  104.         if (v == p)
  105.             continue;
  106.         if (v != specialChild)
  107.         {
  108.             chainNo++;
  109.             HLD(v, u);
  110.         }
  111.     }
  112. }
  113. struct SegmentTree
  114. {
  115.     int maxValue;
  116.     void assignLeaf(int val)
  117.     {
  118.         maxValue = val;
  119.     }
  120.     void Merge(SegmentTree &L, SegmentTree &R)
  121.     {
  122.         if (L.maxValue == inf)
  123.             maxValue = R.maxValue;
  124.         else if (R.maxValue == inf)
  125.             maxValue = L.maxValue;
  126.         else
  127.             maxValue = max(L.maxValue, R.maxValue);
  128.     }
  129. } TREE[MAXN << 2];
  130. void BUILD(int node, int a, int b)
  131. {
  132.     if (a > b)
  133.         return;
  134.     if (a == b)
  135.     {
  136.         TREE[node].assignLeaf(baseArray[a]);
  137.         return;
  138.     }
  139.     int left = node << 1;
  140.     int right = left | 1;
  141.     int mid = (a + b) >> 1;
  142.     BUILD(left, a, mid);
  143.     BUILD(right, mid+1, b);
  144.     TREE[node].Merge(TREE[left], TREE[right]);
  145. }
  146. void UPDATE(int node, int a, int b, int pos, int value)
  147. {
  148.     if (a > b || a > pos || b < pos)
  149.         return;
  150.     if (a >= pos && b <= pos)
  151.     {
  152.         TREE[node].assignLeaf(value);
  153.         return;
  154.     }
  155.     int left = node << 1;
  156.     int right = left | 1;
  157.     int mid = (a + b) >> 1;
  158.     UPDATE(left, a, mid, pos, value);
  159.     UPDATE(right, mid+1, b, pos, value);
  160.     TREE[node].Merge(TREE[left], TREE[right]);
  161. }
  162.  
  163. SegmentTree QUERY(int node, int a, int b, int i, int j)
  164. {
  165.     if (a > b || a > j || b < i)
  166.         return {inf};
  167.     if (a >= i && b <= j)
  168.         return TREE[node];
  169.     int left = node << 1;
  170.     int right = left | 1;
  171.     int mid = (a+b) >> 1;
  172.     SegmentTree p1, p2, res;
  173.     p1 = QUERY(left, a, mid, i, j);
  174.     p2 = QUERY(right, mid+1, b, i, j);
  175.     res.Merge(p1, p2);
  176.     return res;
  177. }
  178.  
  179. void CHANGE_EDGE_COST(int edgeNum, int value)
  180. {
  181.     int endNodeEdge = endNode[edgeNum];
  182.     edgeCost[endNodeEdge] = value;
  183.     UPDATE(1, S, E, posBase[endNodeEdge], value);
  184. }
  185.  
  186. int QUERY_UP(int u, int v)
  187. {
  188.     // u - alwayes the lowest node, v - lca
  189.     int uChain,
  190.         vChain = chainInd[v],
  191.         maxCost = inf;    
  192.     while (true)
  193.     {
  194.         uChain = chainInd[u];
  195.         if (uChain == vChain)
  196.         {
  197.             int l = posBase[v]+1;  // if node query then don’t add 1
  198.             int r = posBase[u];
  199.             if (l > r)
  200.                 break;
  201.             int ans = QUERY(1, S, E, l, r).maxValue;
  202.             maxCost = max(maxCost, ans);
  203.             break;
  204.         }
  205.         int l = posBase[chainHead[uChain]];
  206.         int r = posBase[u];
  207.         maxCost = max(maxCost, QUERY(1, S, E, l, r).maxValue);
  208.         u = father[chainHead[uChain]][0];
  209.     }
  210.     return maxCost;
  211. }
  212.  
  213. int QUERY_HLD(int u, int v)
  214. {
  215.     if (u == v)
  216.         return 0;
  217.     int lca = LCA(u, v);
  218.     int ans = inf;
  219.     if (u != lca)
  220.         ans = max(ans, QUERY_UP(u, lca));
  221.     if (v != lca)
  222.         ans = max(ans, QUERY_UP(v, lca));
  223.     return ans;
  224. }
  225.  
  226. void INITIALIZE()
  227. {
  228.     ptr = 0;
  229.     chainNo = 0;
  230.     for (int i = 0; i < MAXN; i++)
  231.     {
  232.         G[i].clear();
  233.         subTreeSize[i] = 0;
  234.         chainHead[i] = -1;
  235.         chainInd[i] = 0;
  236.         depth[i] = 0;
  237.         baseArray[i] = 0;
  238.         posBase[i] = 0;
  239.         for (int j = 0; j < LOGN; j++)
  240.             father[i][j] = 0;
  241.     }
  242. }
  243.  
  244. int main()
  245. {
  246.     int tc;
  247.     scanf("%d", &tc);
  248.     while (tc--)
  249.     {
  250.         INITIALIZE();
  251.         int tNode;
  252.         scanf("%d", &tNode);
  253.  
  254.  
  255.  
  256.         for (int e = 1; e < tNode; e++)
  257.         {
  258.             int u, v, w;
  259.             scanf("%d %d %d", &u, &v, &w);
  260.             G[u].push_back({v, e, w});
  261.             G[v].push_back({u, e, w});
  262.         }
  263.  
  264.         int root = 1;
  265.         edgeCost[1] = inf;
  266.         depth[root] = 1;
  267.         DFS();
  268.         HLD();
  269.         S = 1;
  270.         E = ptr;
  271.         BUILD(1, S, E);
  272.         char t[7];
  273.         while (true)
  274.         {
  275.             scanf("%s", t);
  276.             if (t[0] == 'D')
  277.                 break;
  278.             if (t[0] == 'C')
  279.             {
  280.                 int edgeNum, value;
  281.                 scanf("%d %d", &edgeNum, &value);
  282.                 CHANGE_EDGE_COST(edgeNum, value);
  283.             }
  284.             else
  285.             {
  286.                 int a, b;
  287.                 scanf("%d %d", &a, &b);
  288.                 int ans = QUERY_HLD(a, b);
  289.                 printf("%d\n", ans);
  290.             }
  291.         }
  292.     }
  293. }
  294. Sample Input:
  295.             1
  296.             3
  297.             1 2 1
  298.             2 3 2
  299.             QUERY 1 2
  300.             CHANGE 1 3
  301.             QUERY 1 2
  302.             DONE
  303. Sample Output:
  304.             1
  305.             3
  306. #define inf                  -123456789
  307.  
  308. static const int MAXN = 1e5 + 5;
  309. static const int LOGN = 18;
  310.  
  311. int     chainNo,            // number of chain
  312.         chainHead[MAXN],    // starting node of the chain
  313.         chainInd[MAXN],     // chain no of a node
  314.         chainPos[MAXN],     // position in the chain in the chain
  315.         chainSize[MAXN],    // total no of node in the chain
  316.         baseArray[MAXN],    // create an array using all chain
  317.         posBase[MAXN],      // position of a node in baseArray
  318.         ptr,                // pointer of baseArray
  319.         depth[MAXN],        // depth of a node in dfs tree
  320.         father[MAXN][LOGN], // sparse table
  321.         subTreeSize[MAXN],  // subtree size of a node
  322.         startNode[MAXN],    // start node of an edge in dfs tree
  323.         endNode[MAXN],      // end node of an edge in dfs tree
  324.         S,                  // starting index of baseArray in Segment tree
  325.         E,                  // last index of baseArray
  326.         edgeCost[MAXN];     // cost of an edge store in a node wrt to dfs tree      
  327. struct node
  328. {
  329.     int v, e, w;  // v: child node, e: edge number, w: edge cost
  330.     node(int vv = 0, int ee = 0, int ww = 0) : v(vv), e(ee), w(ww) {}
  331. };
  332. vector <node> G[MAXN];
  333.  
  334. void DFS(int u = 1, int p = -1)
  335. {
  336.     for (int i = 1; i < LOGN; i++)
  337.         father[u][i] = father[father[u][i-1]][i-1];
  338.     subTreeSize[u] = 1;
  339.  
  340.  
  341.     for (auto &it : G[u])
  342.     {
  343.         int v = it.v;
  344.         int e = it.e;
  345.         int w = it.w;
  346.         if (v == p)
  347.             continue;
  348.         depth[v] = depth[v] + 1;
  349.         father[v][0] = u;
  350.         startNode[e] = u;
  351.         endNode[e] = v;   // use it to update an edge
  352.         edgeCost[v] = w;
  353.         DFS(v, u);
  354.         subTreeSize[u] += subTreeSize[v];
  355.     }
  356. }
  357.  
  358. int LCA(int u, int v)
  359. {
  360.     if (depth[u] < depth[v])
  361.         swap(u, v);
  362.     for (int i = LOGN-1; i >= 0; i--)
  363.     {
  364.         if (depth[father[u][i]] >= depth[v])
  365.         {
  366.             u = father[u][i];
  367.         }
  368.     }
  369.     if (u == v)
  370.         return u;
  371.     for (int i = LOGN-1; i >= 0; i--)
  372.     {
  373.         if (father[u][i] != father[v][i])
  374.         {
  375.             u = father[u][i];
  376.             v = father[v][i];
  377.         }
  378.     }
  379.     return father[u][0];
  380. }
  381.  
  382. void HLD(int u = 1, int p = -1) // nodes are numbered from 1,2,3,………… ,n
  383. {
  384.     if (chainHead[chainNo] == -1)
  385.         chainHead[chainNo] = u;
  386.     chainInd[u] = chainNo;
  387.     ptr++;
  388.     baseArray[ptr] = edgeCost[u];
  389.     posBase[u] = ptr;
  390.     int specialChild = -1;
  391.     int maxSize = -1;
  392.  
  393.  
  394.  
  395.  
  396.     for (auto &it : G[u])
  397.     {
  398.         int v = it.v;
  399.         if (v == p)
  400.             continue;
  401.         if (subTreeSize[v] > maxSize)
  402.             maxSize = subTreeSize[v], specialChild = v;
  403.     }
  404.     if (specialChild != -1)
  405.         hld(specialChild, u);
  406.     for (auto &it : G[u])
  407.     {
  408.         int v = it.v;
  409.         if (v == p)
  410.             continue;
  411.         if (v != specialChild)
  412.         {
  413.             chainNo++;
  414.             HLD(v, u);
  415.         }
  416.     }
  417. }
  418. struct SegmentTree
  419. {
  420.     int maxValue;
  421.     void assignLeaf(int val)
  422.     {
  423.         maxValue = val;
  424.     }
  425.     void Merge(SegmentTree &L, SegmentTree &R)
  426.     {
  427.         if (L.maxValue == inf)
  428.             maxValue = R.maxValue;
  429.         else if (R.maxValue == inf)
  430.             maxValue = L.maxValue;
  431.         else
  432.             maxValue = max(L.maxValue, R.maxValue);
  433.     }
  434. } TREE[MAXN << 2];
  435. void BUILD(int node, int a, int b)
  436. {
  437.     if (a > b)
  438.         return;
  439.     if (a == b)
  440.     {
  441.         TREE[node].assignLeaf(baseArray[a]);
  442.         return;
  443.     }
  444.     int left = node << 1;
  445.     int right = left | 1;
  446.     int mid = (a + b) >> 1;
  447.     BUILD(left, a, mid);
  448.     BUILD(right, mid+1, b);
  449.     TREE[node].Merge(TREE[left], TREE[right]);
  450. }
  451. void UPDATE(int node, int a, int b, int pos, int value)
  452. {
  453.     if (a > b || a > pos || b < pos)
  454.         return;
  455.     if (a >= pos && b <= pos)
  456.     {
  457.         TREE[node].assignLeaf(value);
  458.         return;
  459.     }
  460.     int left = node << 1;
  461.     int right = left | 1;
  462.     int mid = (a + b) >> 1;
  463.     UPDATE(left, a, mid, pos, value);
  464.     UPDATE(right, mid+1, b, pos, value);
  465.     TREE[node].Merge(TREE[left], TREE[right]);
  466. }
  467.  
  468. SegmentTree QUERY(int node, int a, int b, int i, int j)
  469. {
  470.     if (a > b || a > j || b < i)
  471.         return {inf};
  472.     if (a >= i && b <= j)
  473.         return TREE[node];
  474.     int left = node << 1;
  475.     int right = left | 1;
  476.     int mid = (a+b) >> 1;
  477.     SegmentTree p1, p2, res;
  478.     p1 = QUERY(left, a, mid, i, j);
  479.     p2 = QUERY(right, mid+1, b, i, j);
  480.     res.Merge(p1, p2);
  481.     return res;
  482. }
  483.  
  484. void CHANGE_EDGE_COST(int edgeNum, int value)
  485. {
  486.     int endNodeEdge = endNode[edgeNum];
  487.     edgeCost[endNodeEdge] = value;
  488.     UPDATE(1, S, E, posBase[endNodeEdge], value);
  489. }
  490.  
  491. int QUERY_UP(int u, int v)
  492. {
  493.     // u - alwayes the lowest node, v - lca
  494.     int uChain,
  495.         vChain = chainInd[v],
  496.         maxCost = inf;    
  497.     while (true)
  498.     {
  499.         uChain = chainInd[u];
  500.         if (uChain == vChain)
  501.         {
  502.             int l = posBase[v]+1;  // if node query then don’t add 1
  503.             int r = posBase[u];
  504.             if (l > r)
  505.                 break;
  506.             int ans = QUERY(1, S, E, l, r).maxValue;
  507.             maxCost = max(maxCost, ans);
  508.             break;
  509.         }
  510.         int l = posBase[chainHead[uChain]];
  511.         int r = posBase[u];
  512.         maxCost = max(maxCost, QUERY(1, S, E, l, r).maxValue);
  513.         u = father[chainHead[uChain]][0];
  514.     }
  515.     return maxCost;
  516. }
  517.  
  518. int QUERY_HLD(int u, int v)
  519. {
  520.     if (u == v)
  521.         return 0;
  522.     int lca = LCA(u, v);
  523.     int ans = inf;
  524.     if (u != lca)
  525.         ans = max(ans, QUERY_UP(u, lca));
  526.     if (v != lca)
  527.         ans = max(ans, QUERY_UP(v, lca));
  528.     return ans;
  529. }
  530.  
  531. void INITIALIZE()
  532. {
  533.     ptr = 0;
  534.     chainNo = 0;
  535.     for (int i = 0; i < MAXN; i++)
  536.     {
  537.         G[i].clear();
  538.         subTreeSize[i] = 0;
  539.         chainHead[i] = -1;
  540.         chainInd[i] = 0;
  541.         depth[i] = 0;
  542.         baseArray[i] = 0;
  543.         posBase[i] = 0;
  544.         for (int j = 0; j < LOGN; j++)
  545.             father[i][j] = 0;
  546.     }
  547. }
  548.  
  549. int main()
  550. {
  551.     int tc;
  552.     scanf("%d", &tc);
  553.     while (tc--)
  554.     {
  555.         INITIALIZE();
  556.         int tNode;
  557.         scanf("%d", &tNode);
  558.  
  559.  
  560.  
  561.         for (int e = 1; e < tNode; e++)
  562.         {
  563.             int u, v, w;
  564.             scanf("%d %d %d", &u, &v, &w);
  565.             G[u].push_back({v, e, w});
  566.             G[v].push_back({u, e, w});
  567.         }
  568.  
  569.         int root = 1;
  570.         edgeCost[1] = inf;
  571.         depth[root] = 1;
  572.         DFS();
  573.         HLD();
  574.         S = 1;
  575.         E = ptr;
  576.         BUILD(1, S, E);
  577.         char t[7];
  578.         while (true)
  579.         {
  580.             scanf("%s", t);
  581.             if (t[0] == 'D')
  582.                 break;
  583.             if (t[0] == 'C')
  584.             {
  585.                 int edgeNum, value;
  586.                 scanf("%d %d", &edgeNum, &value);
  587.                 CHANGE_EDGE_COST(edgeNum, value);
  588.             }
  589.             else
  590.             {
  591.                 int a, b;
  592.                 scanf("%d %d", &a, &b);
  593.                 int ans = QUERY_HLD(a, b);
  594.                 printf("%d\n", ans);
  595.             }
  596.         }
  597.     }
  598. }
  599. Sample Input:
  600.             1
  601.             3
  602.             1 2 1
  603.             2 3 2
  604.             QUERY 1 2
  605.             CHANGE 1 3
  606.             QUERY 1 2
  607.             DONE
  608. Sample Output:
  609.             1
  610.             3
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!