SHARE
TWEET

Untitled

a guest Sep 30th, 2015 170 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<vector>
  3. #include<algorithm>
  4. #include<cstdio>
  5. #include<cassert>
  6. using namespace std;
  7. vector<int>g[100007];
  8. int parent[100007][22];
  9. int sz[100007];
  10. bool used[100007];
  11. int block[100007], blockpos[100007];
  12. int tin[100007], tout[100007], h[100007];
  13. int timer = 1;
  14. void dfs(int v, int p = 1, int curh = 1)
  15. {
  16.         used[v] = true;
  17.         parent[v][0] = p;
  18.         sz[v] = 1;
  19.         h[v] = curh;
  20.         tin[v] = timer;
  21.         timer++;
  22.         for (int j = 1; j < 22; j++)
  23.         {
  24.                 parent[v][j] = parent[parent[v][j - 1]][j - 1];
  25.         }
  26.         for (int i = 0; i < g[v].size(); i++)
  27.         {
  28.                 int to = g[v][i];
  29.                 if (!used[to])
  30.                 {
  31.                         dfs(to, v, curh + 1);
  32.                         sz[v] += sz[to];
  33.                 }
  34.         }
  35.         tout[v] = timer;
  36.         timer++;
  37. }
  38. bool isHeavy(int u, int v)
  39. {
  40.         if (sz[u] > sz[v]) swap(u, v); 
  41.         return 2 * sz[u] > sz[v];
  42. }
  43. bool isAncestor(int u, int v)
  44. {
  45.         return tin[u] < tin[v] && tout[u] > tout[v];
  46. }
  47. struct segment_tree
  48. {
  49.         vector<long long>tree;
  50.         void init(int n)
  51.         {
  52.                 tree.resize(4 * n + 2);
  53.         }
  54.         void add(int v, int tl, int tr, int pos, int val)
  55.         {
  56.                 if (tl == tr)
  57.                 {
  58.                         tree[v] += val;
  59.                 }
  60.                 else
  61.                 {
  62.                         int tm = (tl + tr) / 2;
  63.                         if (pos <= tm)
  64.                         {
  65.                                 add(2 * v, tl, tm, pos, val);
  66.                         }
  67.                         else
  68.                         {
  69.                                 add(2 * v + 1, tm + 1, tr, pos, val);
  70.                         }
  71.                         tree[v] = max(tree[2 * v], tree[2 * v + 1]);
  72.                 }
  73.         }
  74.         long long getMax(int v, int tl, int tr, int l, int r)
  75.         {
  76.                 if (r<tl || l>tr) return 0;
  77.                 if (tl >= l && tr <= r) return tree[v];
  78.                 int tm = (tl + tr) / 2;
  79.                 return max(getMax(2 * v, tl, tm, l, r), getMax(2 * v + 1, tm + 1, tr, l, r));
  80.         }
  81. };
  82. struct hldBlock
  83. {
  84.         segment_tree st;
  85.         int downv, upv, size;
  86.         void init(int _downv, int _upv, int _size)
  87.         {
  88.                 downv = _downv;
  89.                 upv = _upv;
  90.                 size = _size;
  91.                 st.init(size + 1);
  92.         }
  93.         long long get(int u, int v)
  94.         {
  95.                 if (isAncestor(u, upv) || isAncestor(downv, v))
  96.                 {
  97.                         return 0;
  98.                 }
  99.                 int l = downv, r = upv;
  100.                 if (isAncestor(u, downv))
  101.                 {
  102.                         l = u;
  103.                 }
  104.                 if (isAncestor(upv, v))
  105.                 {
  106.                         r = v;
  107.                 }
  108.                 return st.getMax(1, 1, size, blockpos[l], blockpos[r]);
  109.         }
  110.         void change(int v, int val)
  111.         {
  112.                 st.add(1, 1, size, blockpos[v], val);
  113.         }
  114. };
  115. hldBlock blocks[100007];
  116. void buildDecomposition(int n)
  117. {
  118.         dfs(1);
  119.         int bcnt = 1;
  120.         for (int i = 1; i <= n; i++)
  121.         {
  122.                 bool hasHeavy = false;
  123.                 for (int j = 0; j < g[i].size(); j++)
  124.                 {
  125.                         int to = g[i][j];
  126.                         if (to == parent[i][0]) continue;
  127.                         if (isHeavy(i, to)) hasHeavy = true;
  128.                 }
  129.                 if (!hasHeavy)
  130.                 {
  131.                         vector<int>cur;
  132.                         int j = i;
  133.                         while (j != 1 && isHeavy(j, parent[j][0]))
  134.                         {
  135.                                 assert(block[j] == 0);
  136.                                 cur.push_back(j);
  137.                                 j = parent[j][0];                              
  138.                         }                      
  139.                         if (cur.size() == 0 || isHeavy(cur.back(), j))
  140.                         {
  141.                                 assert(block[j] == 0);
  142.                                 cur.push_back(j);
  143.                         }
  144.                         blocks[bcnt].init(cur[0], cur.back(), cur.size() + 1);
  145.                         for (int i = 0; i < cur.size(); i++)
  146.                         {
  147.                                 int cv = cur[i];
  148.                                 block[cv] = bcnt;
  149.                                 blockpos[cv] = i + 1;
  150.                         }
  151.                         bcnt++;
  152.                 }
  153.         }
  154. }
  155. int getLca(int u, int v)
  156. {
  157.         if (isAncestor(u, v)) return u;
  158.         if (isAncestor(v, u)) return v;
  159.         if (u == v) return u;
  160.         for (int i = 20; i >= 0; i--)
  161.         {
  162.                 if (!isAncestor(parent[u][i], v))
  163.                 {
  164.                         u = parent[u][i];
  165.                 }
  166.         }
  167.         return parent[u][0];
  168. }
  169. long long solvePath(int u, int v)
  170. {
  171.         int curb = block[u];
  172.         long long ans = 0;
  173.         while (1)
  174.         {
  175.                 ans = max(ans, blocks[curb].get(u, v));
  176.                 if (blocks[curb].upv == 1) break;
  177.                 curb = block[parent[blocks[curb].upv][0]];
  178.         }
  179.         return ans;
  180. }
  181. long long getMax(int u, int v)
  182. {
  183.         int lca = getLca(u, v);
  184.         return max(solvePath(u, lca), solvePath(v, lca));
  185. }
  186. void change(int v, int val)
  187. {
  188.         blocks[block[v]].change(v, val);
  189. }
  190. int main()
  191. {
  192.         //freopen("input.txt", "r", stdin);
  193.         //freopen("output.txt", "w", stdout);
  194.         int n;
  195.         scanf("%d\n", &n);
  196.         for (int i = 1; i < n; i++)
  197.         {
  198.                 int u, v;
  199.                 scanf("%d %d\n", &u, &v);
  200.                 g[u].push_back(v);
  201.                 g[v].push_back(u);
  202.         }
  203.         buildDecomposition(n);
  204.         for (int i = 1; i <= n; i++)
  205.         {
  206.                 assert(block[i] != 0);
  207.         }
  208.         int q;
  209.         scanf("%d\n", &q);
  210.         for (int i = 1; i <= q; i++)
  211.         {
  212.                 char mode;
  213.                 scanf("%c ", &mode);
  214.                 if (mode == 'I')
  215.                 {
  216.                         int pos, val;
  217.                         scanf("%d %d\n", &pos, &val);
  218.                         change(pos, val);
  219.                 }
  220.                 else
  221.                 {
  222.                         int u, v;
  223.                         scanf("%d %d\n", &u, &v);
  224.                         printf("%lld\n", getMax(u, v));
  225.                 }
  226.         }
  227. }
RAW Paste Data
Top