SHARE
TWEET

R

a guest Jun 25th, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef pair<int, int> pii;
  7. typedef pair<long long, long long> pll;
  8. #define ff first
  9. #define ss second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define ub upper_bound
  13. #define lb lower_bound
  14. #define all(x) (x).begin(), (x).end()
  15. #define fap(x) cout << " -- " << #x << ": " << (x) << "\n"
  16. #define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  17. const long long INF = 2000000000000000000LL;    // 2e18
  18. const int inf = 0x3f3f3f3f;
  19. const long double EPS = 1e-9;
  20.  
  21. namespace seg {
  22.     // point update, range query maximum
  23.     const int N = 10000+7;
  24.     ll tr[4*N];
  25.  
  26.     void build() {
  27.         memset(tr, 0, sizeof tr);
  28.     }
  29.  
  30.     // adds x in point p
  31.     void update(int at, int l, int r, int p, ll x) {
  32.         if(l == r) {
  33.             tr[at] = x;
  34.             return ;
  35.         }
  36.        
  37.         int lc = at+at, rc = lc+1, mid = (l+r)/2;
  38.         if(p <= mid) update(lc, l, mid, p, x);
  39.         else update(rc, mid+1, r, p, x);
  40.         tr[at] = max(tr[lc], tr[rc]);
  41.     }
  42.  
  43.     // returns the maximum in lo-hi range
  44.     ll query(int at, int l, int r, int lo, int hi) {
  45.         if(l > hi or r < lo) return -INF;   // minimum value, change accordingly
  46.         if(l >= lo and r <= hi) return tr[at];
  47.  
  48.         int lc = at+at, rc = lc+1, mid = (l+r)/2;
  49.         return max(query(lc, l, mid, lo, hi), query(rc, mid+1, r, lo, hi));
  50.     }
  51. };
  52.  
  53. /**
  54.  * Heavy Light Decomposition
  55.  * Build Complexity O(n)
  56.  * Query Complexity O(lg^2 n)
  57.  * Call init() with number of nodes
  58.  * It's probably for the best to not do "using namespace hld"
  59. **/
  60. namespace hld {
  61.     /**
  62.      * N is the maximum number of nodes
  63.      * g is the adjacency graph
  64.      * par, lev, size corresponds to parent, depth, subtree-size
  65.      * head[u] is the starting node of the chain u is in
  66.      * in[u] to out[u] keeps the subtree indices
  67.     **/
  68.     const int N = 10000+7;
  69.     vector<int> g[N];
  70.     int par[N], lev[N], head[N], size[N], in[N], out[N];
  71.     int cur_pos, n;
  72.  
  73.     /**
  74.      * returns the size of subtree rooted at u
  75.      * maintains the child with the largest subtree at the front of g[u]
  76.     **/
  77.     int dfs(int u, int p) {
  78.         int sz = 1;
  79.         for(auto &v : g[u]) {
  80.             if(v == p) continue;
  81.             sz += dfs(v, u);
  82.             if(size[v] > size[g[u].front()]) {
  83.                 swap(v, g[u].front());
  84.             }
  85.         }
  86.  
  87.         par[u] = p;
  88.         lev[u] = lev[p] + 1;
  89.         return size[u] = sz;
  90.     }
  91.  
  92.     /**
  93.      * decomposed the tree in an array
  94.      * note that there is no physical array here
  95.     **/
  96.     void decompose(int u, int p) {
  97.         in[u] = ++cur_pos;
  98.         for(auto &v : g[u]) {
  99.             if(v == p) continue;
  100.             head[v] = (v == g[u].front() ? head[u] : v);
  101.             decompose(v, u);
  102.         }
  103.         out[u] = cur_pos;
  104.     }
  105.  
  106.     /**
  107.      * initializes the structure with _n nodes
  108.     **/
  109.     void init(int _n) {
  110.         n = _n;
  111.         cur_pos = 0;
  112.         dfs(1, 0);
  113.         head[1] = 1;
  114.         decompose(1, 0);
  115.     }
  116.  
  117.     /**
  118.      * checks whether p is an ancestor of u
  119.     **/
  120.     bool isances(int p, int u) {
  121.         return in[p] <= in[u] and out[u] <= out[p];
  122.     }
  123.  
  124.     /**
  125.      * Returns the maximum node value in the path u - v
  126.     **/
  127.     ll query(int u, int v) {
  128.         ll ret = -INF;
  129.         const int LIM = 4000;
  130.         int cnt = 0;
  131.         while(!isances(head[u], v)) {
  132.             ret = max(ret, seg::query(1, 1, n, in[head[u]], in[u]));
  133.             u = par[head[u]];
  134.             assert(++cnt < LIM);
  135.         }
  136.         swap(u, v);
  137.         cnt = 0;
  138.         while(!isances(head[u], v)) {
  139.             ret = max(ret, seg::query(1, 1, n, in[head[u]], in[u]));
  140.             u = par[head[u]];
  141.             assert(++cnt < LIM);
  142.         }
  143.         if(in[v] < in[u]) swap(u, v);
  144.         ret = max(ret, seg::query(1, 1, n, in[u]+1, in[v]));
  145.         return ret;
  146.     }
  147.  
  148.     /**
  149.      * Assigns val to node u
  150.     **/
  151.     void update(int u, ll val) {
  152.         seg::update(1, 1, n, in[u], val);
  153.     }
  154. };
  155.  
  156. int main() {
  157.     FastIO;
  158.  
  159.     int t, tc=0;
  160.     cin >> t;
  161.  
  162.     while(t--) {
  163.         int n;
  164.         cin >> n;
  165.         vector< vector<int> > edg;
  166.         for(int i=1; i<n; ++i) {
  167.             int u, v, w;
  168.             cin >> u >> v >> w;
  169.             edg.push_back({u, v, w});
  170.             hld::g[u].push_back(v);
  171.             hld::g[v].push_back(u);
  172.         }
  173.  
  174.         hld::init(n);
  175.         seg::build();
  176.  
  177.         for(auto &e : edg) {
  178.             if(e[1] == hld::par[e[0]]) swap(e[0], e[1]);
  179.             hld::update(e[1], e[2]);
  180.         }
  181.  
  182.         string op;
  183.         while(cin >> op) {
  184.             if(op == "QUERY") {
  185.                 int u, v;
  186.                 cin >> u >> v;
  187.                 cout << hld::query(u, v) << "\n";
  188.             }
  189.             else if(op == "CHANGE") {
  190.                 int p, w;
  191.                 cin >> p >> w;
  192.                 hld::update(edg[--p][1], w);
  193.             }
  194.             else break;
  195.         }
  196.  
  197.         for(int i=1; i<=n; ++i) hld::g[i].clear();
  198.     }
  199.  
  200.     return 0;
  201. }
RAW Paste Data
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!
 
Top