fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cstring>
  5. #include <climits>
  6.  
  7. using namespace std;
  8.  
  9. struct edge
  10. {
  11.     int u, v, w, c, ci;
  12.     edge(int u, int v, int w, int c, int ci)
  13.         : u(u), v(v), w(w), c(c), ci(ci) {}
  14. };
  15.  
  16. struct vertex
  17. {
  18.     int p, d, se, c, ci;
  19.     vector<int> a;
  20.     vector<int> lca;
  21.     vertex():
  22.         p(-1),d(0),se(-1),c(-1),ci(-1),a(),lca() {}
  23. };
  24.  
  25. struct chain
  26. {
  27.     int je, h;
  28.     vector<int> e, st;
  29.     chain(int je, int h): je(je), h(h) {}
  30. };
  31.  
  32. struct graph
  33. {
  34.     vector<edge> e;
  35.     vector<vertex> v;
  36.     vector<chain> c;
  37. };
  38.  
  39. void hld(int u, int c, int ci, graph& g);
  40. int dfs(int u, int p, graph& g);
  41. int log2(int n);
  42. void comp_lca(graph &g);
  43. int lca(int u, int v, graph &g);
  44. void create_sts(graph &g);
  45. int build_st(int ci, int idx, int l, int r, graph &g);
  46. void update(int ci, int idx, int l, int r, int i, int nv, graph& g);
  47. int path_max(int u, int v, graph& g);
  48.  
  49. int main()
  50. {
  51.     int t, n, u, v, w;
  52.     graph g;
  53.     char q[10];
  54.  
  55.     scanf("%d", &t);
  56.     while(t--)
  57.     {
  58.         scanf("%d", &n);
  59.  
  60.         g.e.clear();
  61.         g.v.clear();
  62.         g.c.clear();
  63.         g.v.resize(n, vertex());
  64.  
  65.         for(int i = 0; i < n-1; i++)
  66.         {
  67.             scanf("%d %d %d", &u, &v, &w);
  68.             u--; v--;
  69.             g.e.push_back(edge(u, v, w, -1, -1));
  70.             g.v[u].a.push_back(i);
  71.             g.v[v].a.push_back(i);
  72.         }
  73.  
  74.         dfs(0, -1, g);        
  75.         g.c.push_back(chain(-1, 0));
  76.         hld(0, 0, 0, g);
  77.         comp_lca(g);
  78.         create_sts(g);
  79.  
  80.         while(true)
  81.         {
  82.             scanf("%s", q);
  83.  
  84.             if(strcmp(q, "DONE") == 0)
  85.                 break;
  86.  
  87.             scanf("%d %d", &u, &v);
  88.  
  89.             if(strcmp(q, "QUERY") == 0)
  90.             {
  91.                 u--; v--;
  92.                 w = lca(u, v, g);
  93.                 if(u == v)
  94.                     printf("0\n");
  95.                 else
  96.                     printf("%d\n", max(path_max(u, w, g), path_max(v, w, g)));
  97.             }
  98.  
  99.             if(strcmp(q, "CHANGE") == 0)
  100.             {
  101.                 u--;
  102.                 g.e[u].w = v;
  103.  
  104.                 if(g.e[u].c != -1)
  105.                     update(g.e[u].c,
  106.                            0, 0, g.c[g.e[u].c].e.size()-1,
  107.                            g.e[u].ci, v, g);
  108.             }
  109.         }        
  110.     }
  111.  
  112.     return 0;
  113. }
  114.  
  115. int dfs(int u, int p, graph& g)
  116. {
  117.     int count, m_count, t_count, v, se;
  118.     vector<int>::iterator it;
  119.  
  120.     count = 1;
  121.     m_count = 0;
  122.     se = -1;
  123.     g.v[u].p = p;
  124.     g.v[u].d = p == -1 ? 1 : g.v[p].d + 1;
  125.  
  126.     for(it = g.v[u].a.begin(); it != g.v[u].a.end(); it++)
  127.     {
  128.         v = u ^ g.e[*it].u ^ g.e[*it].v;
  129.  
  130.         if(v == p)
  131.             continue;
  132.  
  133.         t_count = dfs(v, u, g);
  134.         count += t_count;
  135.  
  136.         if(t_count > m_count)
  137.         {
  138.             m_count = t_count;
  139.             se = *it;
  140.         }
  141.     }
  142.  
  143.     g.v[u].se = se;
  144.     return count;
  145. }
  146.  
  147. void hld(int u, int c, int ci, graph& g)
  148. {
  149.     int v, se;
  150.     vector<int>::iterator it;
  151.  
  152.     g.v[u].c = c;
  153.     g.v[u].ci = ci;
  154.     se = g.v[u].se;
  155.  
  156.     if(se == -1)
  157.         return;
  158.  
  159.     v = u ^ g.e[se].u ^ g.e[se].v;
  160.     g.e[se].c = c;
  161.     g.c[c].e.push_back(se);
  162.     g.e[se].ci = g.c[c].e.size()-1;
  163.  
  164.  
  165.     hld(v, c, ci+1, g);
  166.  
  167.     for(it = g.v[u].a.begin(); it != g.v[u].a.end(); it++)
  168.     {
  169.         v = u ^ g.e[*it].u ^ g.e[*it].v;
  170.  
  171.         if(v == g.v[u].p || *it == se)
  172.             continue;
  173.  
  174.         g.c.push_back(chain(*it, v));
  175.         hld(v, g.c.size()-1, 0, g);
  176.     }
  177. }
  178.  
  179. int log2(int n)
  180. {
  181.     int e = 0, te = 1;
  182.     while(te < n)
  183.     {
  184.         te *= 2;
  185.         e++;
  186.     }
  187.     return e;
  188. }
  189.  
  190. void comp_lca(graph &g)
  191. {
  192.     int maxj = log2(g.v.size());
  193.  
  194.     for(int i = 0; i < g.v.size(); i++)
  195.     {
  196.         g.v[i].lca.resize(maxj+1, -1);
  197.         g.v[i].lca[0] = g.v[i].p;
  198.     }
  199.  
  200.     for(int j = 1; j <= maxj; j++)
  201.     {
  202.         for(int i = 0; i < g.v.size(); i++)
  203.         {            
  204.             if(g.v[i].lca[j-1] != -1)
  205.                 g.v[i].lca[j] = g.v[g.v[i].lca[j-1]].lca[j-1];
  206.             else
  207.                 g.v[i].lca[j] = -1;
  208.         }
  209.     }
  210. }
  211.  
  212. int lca(int u, int v, graph &g)
  213. {
  214.     int diff = g.v[v].d - g.v[u].d, j;
  215.  
  216.     if(diff < 0)
  217.         return lca(v, u, g);
  218.  
  219.     j = 0;
  220.     while(diff > 0)
  221.     {
  222.         if(diff % 2)
  223.             v = g.v[v].lca[j];
  224.         diff /= 2;
  225.         j++;
  226.     }
  227.  
  228.     if(u == v)
  229.         return u;
  230.  
  231.     while(g.v[u].p != g.v[v].p)
  232.     {
  233.         j = 0;
  234.         while(g.v[u].lca[j] != g.v[v].lca[j])
  235.             j++;
  236.         u = g.v[u].lca[j-1];
  237.         v = g.v[v].lca[j-1];
  238.     }
  239.  
  240.     return g.v[u].p;
  241. }
  242.  
  243. void create_sts(graph& g)
  244. {
  245.     for(int i = 0; i < g.c.size(); i++)
  246.     {
  247.         if(g.c[i].e.size() == 0)
  248.             continue;
  249.  
  250.         g.c[i].st.resize(4*g.c[i].e.size(), 0);
  251.         build_st(i, 0, 0, g.c[i].e.size()-1, g);
  252.     }    
  253. }
  254.  
  255. int build_st(int ci, int idx, int l, int r, graph &g)
  256. {
  257.     int ridx, lidx, mid;
  258.  
  259.     lidx = (idx<<1)+1;
  260.     ridx = lidx+1;
  261.     mid = (l+r)>>1;
  262.  
  263.     if(l==r)
  264.     {
  265.         g.c[ci].st[idx] = g.e[g.c[ci].e[l]].w;
  266.         return g.c[ci].st[idx];
  267.     }
  268.  
  269.     g.c[ci].st[idx] = max(
  270.         build_st(ci, lidx, l, mid, g),
  271.         build_st(ci, ridx, mid+1, r, g));
  272. }
  273.  
  274. int query(int ci, int idx, int l, int r, int a, int b, graph& g)
  275. {
  276.     int lidx, ridx, mid, mx = INT_MIN;
  277.  
  278.     lidx = (idx<<1)+1;
  279.     ridx = lidx+1;
  280.     mid = (l+r)>>1;
  281.  
  282.     if(l==a && r==b)
  283.         return g.c[ci].st[idx];
  284.     if(a <= mid)
  285.         mx = max(mx, query(ci, lidx, l, mid, a, min(mid,b), g));
  286.     if(b > mid)
  287.         mx = max(mx, query(ci, ridx, mid+1, r, max(mid+1, a), b, g));
  288.     return mx;
  289. }
  290.  
  291. void update(int ci, int idx, int l, int r, int i, int nv, graph& g)
  292. {
  293.     int lidx, ridx, mid;
  294.  
  295.     lidx = (idx<<1)+1;
  296.     ridx = lidx + 1;
  297.     mid = (l+r)>>1;
  298.  
  299.     if(l==r)
  300.     {
  301.         g.c[ci].st[idx] = nv;
  302.         return;
  303.     }
  304.  
  305.     if(i <= mid)
  306.         update(ci, lidx, l, mid, i, nv, g);
  307.     else        
  308.         update(ci, ridx, mid+1, r, i, nv, g);
  309.  
  310.     g.c[ci].st[idx] = max(g.c[ci].st[lidx], g.c[ci].st[ridx]);    
  311. }
  312.  
  313. int path_max(int u, int v, graph &g)
  314. {
  315.     int mx = INT_MIN, i, j;
  316.  
  317.     while(true)
  318.     {
  319.         if(u == v)
  320.             return mx;
  321.  
  322.         i = g.v[u].c == g.v[v].c ? g.v[v].ci : 0;
  323.         j = g.v[u].ci - 1;
  324.         if(j >= 0)
  325.             mx = max(mx, query(g.v[u].c,
  326.                                0, 0, g.c[g.v[u].c].e.size()-1,
  327.                                i, j, g));
  328.  
  329.         if(g.v[u].c == g.v[v].c)
  330.             return mx;
  331.  
  332.         mx = max(mx, g.e[g.c[g.v[u].c].je].w);
  333.         u = g.v[g.c[g.v[u].c].h].p;
  334.     }
  335. }
  336.  
Runtime error #stdin #stdout 0s 16016KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/67s1Ji
qtree
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years ago
visibility:
public

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!