fork download
copy 
  1. #include <cstdio>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. struct Edge;
  8. struct Node {
  9.     Edge *parentedge = NULL;
  10.     int layer;
  11.     int size;
  12.     int chainid;
  13.     vector<Edge *> edges;
  14.  
  15.     Node() {
  16.         layer = -1;
  17.         size = -1;
  18.         chainid = -1;
  19.     }
  20. };
  21.  
  22. struct Edge {
  23.     pair<Node *, Node *> nodes;
  24.     int cost;
  25.     int chainid;
  26.  
  27.     Edge() {
  28.         cost = -1;
  29.         chainid = -1;
  30.     }
  31.  
  32.     Node *getother(Node *currnode) {
  33.         if (currnode == nodes.first) {
  34.             return nodes.second;
  35.         } else {
  36.             return nodes.first;
  37.         }
  38.     }
  39. };
  40.  
  41. int log2(int n) {
  42.     int result = -1;
  43.     while (n) {
  44.         result++;
  45.         n >>= 1;
  46.     }
  47.     return result;
  48. }
  49.  
  50. int pow2(int n) {
  51.     return 1 << n;
  52. }
  53.  
  54. void hld(vector<Node> &nodes, vector<pair<Edge *, Edge*> > &chains, Node *currnode) {
  55.     if (currnode->edges.size() == 1) {
  56.         currnode->size = 1;
  57.         return;
  58.     }
  59.     currnode->size = 1;
  60.     for (int i = 0; i < currnode->edges.size(); i++) {
  61.         Edge *edge = currnode->edges[i];
  62.         Node *next = edge->getother(currnode);
  63.         hld(nodes, chains, next);
  64.         currnode->size += next->size;
  65.     }
  66.  
  67.     for (int i = 0; i < currnode->edges.size(); i++) {
  68.         Edge *edge = currnode->edges[i];
  69.         Node *next = edge->getother(currnode);
  70.         if (next->size * 2 > currnode->size) {
  71.             if (edge->chainid == -1) {
  72.                 edge->chainid = next->chainid = (int) chains.size();
  73.                 chains.push_back(make_pair((Edge *) NULL, edge));
  74.             }
  75.             edge->chainid = currnode->chainid = next->chainid;
  76.             chains[edge->chainid].first = edge;
  77.             break;
  78.         } else if (next->chainid != -1) {
  79.             next->chainid = -1;
  80.         }
  81.     }
  82. }
  83.  
  84. void buildsegtree(vector<int> &segtree, vector<int> &numbers) {
  85.     segtree = vector<int>(pow2(log2((int) numbers.size()) + 1));
  86.     for (int i = 0; i < numbers.size(); i++) {
  87.         segtree[i + segtree.size()/2] = numbers[i];
  88.     }
  89.     for (int i = numbers.size() / 2 - 1; i; i--) {
  90.         segtree[i] = max(segtree[i<<1], segtree[i<<1|1]);
  91.     }
  92. }
  93.  
  94. void segtreeset(vector<int> &segtree, int i, int n) {
  95.     i += segtree.size() / 2;
  96.     segtree[i] = n;
  97.     i >>= 1;
  98.     for (; i; i >>= 1) segtree[i] = max(segtree[i << 1], segtree[i<<1|1]);
  99. }
  100.  
  101. int segtreemaxrange(vector<int> &segtree, int l, int r) {
  102.     int m = 0;
  103.     while (r > l) {
  104.         if (l&1) {
  105.             m = max(m, segtree[l]);
  106.             l++;
  107.         }
  108.         if (~r&1) {
  109.             m = max(m, segtree[r]);
  110.             r--;
  111.         }
  112.         l >>= 1;
  113.         r >>= 1;
  114.         if (r == l)
  115.             m = max(m, segtree[l]);
  116.     }
  117.     return m;
  118. }
  119.  
  120. int main() {
  121.     int t;
  122.     scanf("%d", &t);
  123.     for (int _ = 0; _ < t; _++) {
  124.         int n;
  125.         scanf("%d", &n);
  126.         vector<Node> nodes(n);
  127.         vector<Edge> edges(n - 1);
  128.         for (int i = 0; i < n - 1; i++) {
  129.             int a, b, c;
  130.             scanf("%d %d %d", &a, &b, &c);
  131.             a--;
  132.             b--;
  133.             edges[i].nodes = make_pair(&nodes[a], &nodes[b]);
  134.             edges[i].cost = c;
  135.             nodes[a].edges.push_back(&edges[i]);
  136.             nodes[b].edges.push_back(&edges[i]);
  137.         }
  138.         nodes.front().layer = 0;
  139.         queue<Node *> bfs;
  140.         bfs.push(&nodes.front());
  141.         while (bfs.size()) {
  142.             Node *currnode = bfs.front();
  143.             bfs.pop();
  144.             for (int i = 0; i < currnode->edges.size(); i++) {
  145.                 Edge *edge = currnode->edges[i];
  146.                 Node *next = edge->getother(currnode);
  147.                 if (!next->parentedge) {
  148.                     next->parentedge = edge;
  149.                     next->layer = currnode->layer + 1;
  150.                     bfs.push(next);
  151.                 }
  152.             }
  153.         }
  154.  
  155.         for (int i = 0; i < n - 1; i++) {
  156.             if (edges[i].nodes.first->layer > edges[i].nodes.second->layer) {
  157.                 swap(edges[i].nodes.first, edges[i].nodes.second);
  158.             }
  159.         }
  160.  
  161.         vector<pair<Edge *, Edge *> > chains;
  162.  
  163.         hld(nodes, chains, &nodes.front());
  164.  
  165.         vector<vector<int> > chainsegtrees;
  166.         for (int i = 0; i < chains.size(); i++) {
  167.             pair<Edge *, Edge *> chain = chains[i];
  168.             vector<int> edgelengths(chain.second->nodes.second->layer - chain.first->nodes.second->layer);
  169.             Node *currnode = chain.second->nodes.second;
  170.             while (currnode != chain.first->nodes.first) {
  171.                 edgelengths[currnode->layer - chain.first->nodes.first->layer - 1] = currnode->parentedge->cost;
  172.                 currnode = currnode->parentedge->getother(currnode);
  173.             }
  174.             chainsegtrees.push_back(vector<int>());
  175.             buildsegtree(chainsegtrees.back(), edgelengths);
  176.         }
  177.  
  178.         while (true) {
  179.             char command;
  180.             {
  181.                 do {
  182.                     command = getchar();
  183.                 } while (command == ' ' || command == '\n');
  184.                 char tmp;
  185.                 do {
  186.                     tmp = getchar();
  187.                 } while (tmp != ' ' && tmp != '\n');
  188.             }
  189.             if (command == 'D') {
  190.                 break;
  191.             } else if (command == 'C') {
  192.                 int a, c;
  193.                 scanf("%d %d", &a, &c);
  194.                 a--;
  195.                 edges[a].cost = c;
  196.                 if (edges[a].chainid != -1) {
  197.                     int segi = edges[a].nodes.first->layer - chains[edges[a].chainid].first->nodes.first->layer;
  198.                     segtreeset(chainsegtrees[nodes[a].layer], segi, c);
  199.                 }
  200.             } else {
  201.                 int a, b;
  202.                 scanf("%d %d", &a, &b);
  203.                 a--;
  204.                 b--;
  205.                 Node *nodea = &nodes[a];
  206.                 Node *nodeb = &nodes[b];
  207.                 long long result = 0;
  208.                 while (nodea != nodeb && (nodea->chainid == -1 || nodea->chainid != nodeb->chainid)) {
  209.                     if (nodea->layer > nodeb->layer) {
  210.                         if (nodea->chainid != -1) {
  211.                             nodea = chains[nodea->chainid].first->nodes.first;
  212.                         } else {
  213.                             result = max(result, (long long) nodea->parentedge->cost);
  214.                             nodea = nodea->parentedge->getother(nodea);
  215.                         }
  216.                     } else {
  217.                         if (nodeb->chainid != -1) {
  218.                             nodeb = chains[nodeb->chainid].first->nodes.first;
  219.                         } else {
  220.                             result = max(result, (long long) nodeb->parentedge->cost);
  221.                             nodeb = nodeb->parentedge->getother(nodeb);
  222.                         }
  223.                     }
  224.                 }
  225.                 if (nodea != nodeb && nodea->chainid == nodeb->chainid) {
  226.                     result = max(result, (long long)  segtreemaxrange(chainsegtrees[nodea->chainid],
  227.                                                          nodea->layer - chains[nodea->chainid].first->nodes.first->layer,
  228.                                                          nodeb->layer - chains[nodeb->chainid].first->nodes.first->layer - 1));
  229.                 }
  230.                 printf("%lld\n", result);
  231.             }
  232.         }
  233.     }
  234.     return 0;
  235. }
Success #stdin #stdout 0s 3424KB
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/wtg852
problem QTREE, based on SPOJ submission 16237158 (C++ 5), 2016-02-06 03:35:34
language:
C++ (gcc 8.3)
created:
8 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!