Line Tree?

[lrvideckis]

Can you add a problem which can test https://codeforces.com/blog/entry/71568?#comment-559304 ?

Like maybe: given a weighted, unrooted tree, answer queries of: given u,v find max edge weight on path from u to v

[maspypy]

As for the setting, it is similar to the problem found here, but since this is a special solution for the min/max case, I need to create a new problem.

Therefore, I’m thinking of adding a new problem.

It doesn’t seem necessary for the graph to be a tree, so how about considering the following problem?

Given a connected graph with $N$ edges and $M$ vertices. The edges have weights. The weight of a path is defined as the max of the edges that the path passes through. Answer $Q$ queries: given $s$ and $t$, output the minimum weight of a path from $s$ to $t$.

$N$ $M$ $Q$
$a_0$ $b_0$ $w_0$
$\vdots$
$a_{M-1}$ $b_{M-1}$ $w_{M-1}$
$s_0$ $t_0$
$\vdots$
$s_{Q-1}$ $t_{Q-1}$

Constraints
$2 \leq N \leq 500000$
$N-1 \leq M \leq 500000$
$1 \leq Q \leq 500000$

[lrvideckis]

BTW This should be lower priority IMO because the oj-verify tool supports aizu judge, and there's this problem https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_12_A which you can run line tree against the naive (low bounds)

[lrvideckis]

oh, I noticed you have n-1<=m, but the code I have for line tree works when there's multiple components (in this case, it returns a set of linked lists)

[lrvideckis]

pair<vector<pii>, UF> line_tree(int n, const vector<array<int, 3>>& w_eds) {
  vector<pii> list(n, {-1, -1});  // list[v] = {next node, edge weight}
  vi last(n);
  iota(all(last), 0);
  UF uf(n);
  for (auto [w, u, v] : w_eds) {
    u = uf.find(u), v = uf.find(v);
    if (uf.join(u, v)) {
      int p = uf.find(u);
      list[last[p]] = {p ^ u ^ v, w};
      last[p] = last[p ^ u ^ v];
    }
  }
  return {list, uf};
}

where uf.find(v) = head of linked list of that component

[lrvideckis]

oh BTW I couldn't figure out the O(n) (after sorting edges), mentioned in that comment :( I would be very interested if you know how it's done

my only observation is when you merge 2 lists into 1, you can choose to reverse either list

I also tried applying this A Linear-Time Algorithm for a Special Case
of Disjoint Set Union but I don't think it can be applied, because that paper assumes you know the "dsu tree" already, but given the sorted edges, building the "dsu tree" already takes O(n*ack(n))

[maspypy]

I only know the O(N\alpha(N)) solution.

[maspypy]

I suggest adding the constraint that the graph is connected, as it simplifies the problem statement and has minimal impact on the solution.