Function test

code/graph/hld.test.cpp:78–215

};

void test() {
  /* Field testing: SPOJ LCA, SPOJ QTREE, TOJ 2241, Live Archive 2045, Live Archive 6140, UVa 10938, IPSC 2009 L */

  int ts = 100,
    maxn = 1000,
    maxq = 1000,
    minc = -1000,
    maxc = 1000;

  // ts = 100000;
  // maxn = 4;
  // minc = 1;
  // maxc = 4;
  // maxq = 5;

  for (int t = 0; t < ts; t++)
  {
    // printf("%d\n", t);

    int n = randint(1, maxn),
      qs = maxq;

    HLD hld1(n);
    HLD_naive hld2(n);

    union_find uf(n);
    vii edges;
    vvi adj(n);
    for (int i = 0; i < n - 1; i++)
    {
      while (true)
      {
        int a = randint(0, n - 1),
          b = randint(0, n - 1);

        if (uf.find(a) == uf.find(b))
          continue;

        uf.unite(a, b);
        // hld1.add_edge(a, b);
        // hld2.add_edge(a, b);
        edges.push_back(ii(a, b));
        edges.push_back(ii(b, a));
        adj[a].push_back(b);
        adj[b].push_back(a);
        hld1.add_edge(a,b);
        break;
      }
    }

    vector<int> parent(n, -1);

    stack<int> S;
    vector<bool> visited(n, false);
    int root = randint(0, n - 1);
    visited[root] = true;
    S.push(root);