fork download
copy 
  1. /**********************************************
  2.             Author : smiley007  
  3. ***********************************************/
  4.  
  5. //Data Structure Includes
  6. #include <vector>
  7. #include <queue>
  8. #include <deque>
  9. #include <bitset>
  10. #include <stack>
  11. #include <list>
  12. #include <set>          
  13. #include <map>
  14. #include <unordered_set>
  15.  
  16. //Other Includes
  17. #include <cstdio>
  18. #include <string>
  19. #include <cstring>
  20. #include <cstdlib>
  21. #include <iostream>
  22. #include <cmath>
  23. #include <cctype>
  24. #include <cassert>
  25. #include <numeric>
  26. #include <algorithm>
  27. #include <ctime>
  28. #include <sstream>
  29. #include <climits>
  30. #include <iomanip>
  31.  
  32. using namespace std ;
  33. typedef long long ll;
  34. typedef pair<int,int> pii;
  35. typedef pair<ll,ll> pll;
  36. typedef vector<int> vi;
  37. typedef vector<ll> vll;
  38. typedef vector<vll> vvll;
  39. typedef vector<vvll> vvvll;
  40. typedef vector<pii> vpii;
  41. typedef vector<vpii> vvpii;
  42. typedef vector<vpii> vvpii;
  43. typedef vector<pll> vpll;
  44. typedef vector<vpll> vvpll;
  45. typedef vector<vvpll> vvvpll;
  46. typedef vector<vi> vvi;
  47. typedef vector<string> vs;
  48. typedef vector<vs> vvs;
  49.  
  50. #ifdef LocalHost
  51.     #define eprintf(...) fprintf(stderr,__VA_ARGS__)
  52. #endif
  53.  
  54. //Code Begins Here ------ >>>
  55.  
  56.  
  57. class HLD {
  58.  
  59. private:
  60.     const static int N = 1e4 + 44;
  61.     const static int LN = 14;
  62.     int parent[N], depth[N], subsize[N];
  63.     int chainNum[N], valuePos[N], chainPos[N], chainHead[N] = {-1};
  64.     int tree[2 * N];
  65.     vpii g[N];
  66.     int a[N], b[N];
  67.     int p[N][LN]; //[#node][height from node]
  68.     int currChain = 0; // # of available chains
  69.     int n;
  70.     int ptr = 0;
  71.  
  72. public:
  73.  
  74.     void reset() {
  75.         ptr = 0;
  76.         currChain = 0;
  77.  
  78.         for (int i = 1; i <= n; i++) {
  79.             chainHead[i] = -1;
  80.             g[i].clear();
  81.             for (int j = 0; j < LN; j++)    p[i][j] = -1;
  82.         }
  83.  
  84.     }
  85.  
  86.      void read() {
  87.         scanf("%d", &n);
  88.         reset();
  89.         for (int i = 1; i <= n - 1; i++) {
  90.             int x, y, z;
  91.             scanf("%d %d %d", &x, &y, &z);
  92.             a[i] = x;   b[i] = y;
  93.             g[x].push_back(make_pair(y, z));
  94.             g[y].push_back(make_pair(x, z));
  95.         }
  96.  
  97.     }
  98.  
  99.     void solve() {
  100.  
  101.         dfs(1, 0, -1); 
  102.  
  103.         for (int i = 1; i <= n; i++) {
  104.             p[i][0] = parent[i];
  105.         }
  106.         for (int i = 1; i < LN; i++) {
  107.             for (int j = 1; j <= n; j++) if (p[j][i - 1] != -1){
  108.                 p[j][i] = p[p[j][i - 1]][i - 1];
  109.             }
  110.         }
  111.         make_hld(1, -1, 0);
  112.         build(1, ptr, 1);
  113.  
  114.     }
  115.  
  116.  
  117.  
  118.     /**
  119.     (u -> current node, l -> current level, p -> parent node)
  120.     **/
  121.     void dfs(int u, int l, int p) {
  122.         parent[u] = p;
  123.         depth[u] = l;
  124.         int res = 1;
  125.         for (auto it : g[u]) {
  126.             int v = it.first;
  127.             if (v != p) {
  128.                 dfs(v, l + 1, u);
  129.                 res += subsize[v];
  130.             }
  131.         }
  132.         subsize[u] = res;
  133.         return;
  134.     }
  135.  
  136.     int getLCA(int a, int b) {
  137.         if (depth[a] < depth[b])    swap(a, b);
  138.         int diff = depth[a] - depth[b];
  139.         for (int i = LN - 1; i >= 0; i--)   if ((diff >> i) & 1) {
  140.             a = p[a][i];
  141.         }
  142.         if (a == b) return a;
  143.         for (int i = LN - 1; i >= 0; i--) {
  144.             if (p[a][i] != p[b][i]) {
  145.                 a = p[a][i];
  146.                 b = p[b][i];
  147.             }
  148.         }
  149.         return p[a][0];
  150.     }
  151.  
  152.  
  153.     void make_hld(int curr, int p, int cst) {
  154.         if (chainHead[currChain] == -1) {
  155.             chainHead[currChain] = curr;
  156.         }  
  157.         chainNum[curr] = currChain;
  158.         chainPos[curr] = ++ptr;
  159.         valuePos[ptr] = cst;
  160.         int idx = -1, mx = -1;
  161.         for (int i = 0; i < (int)g[curr].size(); i++) {
  162.             int v = g[curr][i].first;
  163.             if (v != p) {
  164.                 if (mx < subsize[v]) {
  165.                     mx = subsize[v];
  166.                     idx = i;
  167.                 }
  168.             }
  169.         }
  170.         if (idx != -1)  make_hld(g[curr][idx].first, curr, g[curr][idx].second);
  171.         for (int i = 0; i < (int)g[curr].size(); i++) {
  172.             int v = g[curr][i].first;
  173.             if (v != p && i != idx) {
  174.                 currChain++;
  175.                 make_hld(g[curr][i].first, curr, g[curr][i].second);
  176.             }
  177.         }
  178.     }
  179.  
  180.     void build(int l, int r, int idx) {
  181.         if (l == r) {
  182.             tree[idx] = valuePos[l];
  183.             return;
  184.         } 
  185.         int mid = (l + r) >> 1;
  186.         build(l, mid, idx + idx);
  187.         build(mid + 1, r, idx + idx + 1);
  188.         tree[idx] = max(tree[idx + idx], tree[idx + idx + 1]);
  189.     }
  190.  
  191.     void update_tree(int l, int r, int idx, int pos, int val) {
  192.         if (l == r) {
  193.             tree[idx] = val;
  194.             return;
  195.         }
  196.         int mid = (l + r) >> 1;
  197.         if (pos <= mid) update_tree(l, mid, idx + idx, pos, val);
  198.         else    update_tree(mid + 1, r, idx + idx + 1, pos, val);
  199.         tree[idx] = max(tree[idx + idx], tree[idx + idx + 1]);
  200.     }
  201.  
  202.     void update(int numEdge, int cst) {
  203.         int u = a[numEdge];
  204.         int v = b[numEdge];
  205.  
  206.         int pu = chainPos[u];
  207.         int pv = chainPos[v];
  208.  
  209.         update_tree(1, ptr, 1, max(pu, pv), cst);
  210.  
  211.     }
  212.  
  213.     int query_tree(int l, int r, int idx, int a, int b) {
  214.         if (l > b || r < a) return 0;
  215.         if (a <= l && r <= b)   return tree[idx];
  216.         int mid = (l + r) >> 1;
  217.         int ans = query_tree(l, mid, idx + idx, a, b);
  218.         ans = max(ans, query_tree(mid + 1, r, idx + idx + 1, a, b));
  219.         return ans;
  220.     }
  221.  
  222.     int query(int u, int v) {
  223.         int ans = 0;
  224.         while (u != v) {
  225.             int cu = chainNum[u];
  226.             int cv = chainNum[v];
  227.             int pu = chainPos[u];
  228.             int pv = chainPos[v];
  229.             int h = chainHead[cu];
  230.             int ph = chainPos[h];
  231.             if (cu == cv) {   
  232.                 ans = max(ans, query_tree(1, ptr, 1, pv + 1, pu));
  233.                 break;
  234.             } else {
  235.                 ans = max(ans, query_tree(1, ptr, 1, ph, pu));
  236.                 u = parent[h];
  237.             }
  238.         }
  239.         return ans;
  240.     }   
  241.  
  242.  
  243.     // void out() {
  244.     //     cout << "depth : \n";
  245.     //     for (int i = 1; i <= n; i++)
  246.     //         cout << i << " :  " << depth[i] << "\n";
  247.     //     cout << "\n\nparent : \n";
  248.     //     for (int i = 1; i <= n; i++)
  249.     //         cout << i << " :  " << parent[i] << "\n";
  250.     //     cout << "\n\nsubtree size : \n";
  251.     //     for (int i = 1; i <= n; i++)
  252.     //         cout << i << " :  " << subsize[i] << "\n";
  253.     //     cout << "\n";
  254.     //     cout << "currChain : " << currChain << "\n";
  255.     //     for (int i = 0; i <= currChain; i++) {
  256.     //         for (int j = 0; j < chainSize[i]; j++) {
  257.     //             cout << chains[i][j] << " ";
  258.     //         }
  259.     //         cout << "\n\n";
  260.     //     }
  261.     // }
  262.  
  263.  
  264. };
  265.  
  266.  
  267.  
  268. int main(){
  269.     #ifdef LocalHost
  270.         freopen("input.txt","r",stdin);
  271.     #endif
  272.  
  273.     int t;
  274.     cin >> t;
  275.     HLD obj = HLD();
  276.     while (t--) {
  277.         obj.read();
  278.         obj.solve();
  279.         while (true) {
  280.             string s;
  281.             cin >> s;
  282.             if (s[0] == 'D')    break;
  283.             int a, b;
  284.             cin >> a >> b;
  285.             if (s[0] == 'Q') {
  286.                 int lca = obj.getLCA(a, b);
  287.                 cout << max(obj.query(a, lca), obj.query(b, lca)) << "\n";
  288.             } else {
  289.                 obj.update(a, b);
  290.             }
  291.         }
  292.     }
  293.  
  294.  
  295.  
  296.  
  297.  
  298.  
  299.  
  300.  
  301.  
  302.  
  303.  
  304.     #ifdef LocalHost
  305.         cout<<endl<<"Execution time = "<<(float)clock()/CLOCKS_PER_SEC <<" s"<<endl;
  306.     #endif
  307.  
  308.  
  309.  
  310.     return 0;
  311. }
Success #stdin #stdout 0s 17176KB
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/MaDYbs
problem QTREE, based on SPOJ submission 19075614 (CPP), 2017-03-26 16:12:04
language:
C++ (gcc 8.3)
created:
7 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!