Problem: alphabet_adventuring (2022 finals)

Alphonse is assembling an *alphabet tree* and arranging some adventures along the way.

An alphabet tree is an unrooted tree with \(N\) nodes (numbered from \(1\) to \(N\)) and \(N - 1\) edges. Initially, the \(i\)th edge connects nodes \(A_i\) and \(B_i\) in both directions, and is labeled with a uppercase letter \(C_i\). Two edges incident to a common node are always labeled with different letters.

Alphonse has \(Q\) events to process, the \(i\)th of which is one of two types:

* `1` \(U_i\) \(L_i\): Add a new node to the tree by connecting it to node \(U_i\) with a new edge labeled with uppercase letter \(L_i\). Newly added nodes are numbered with integers starting from \(N + 1\) in the order they're added.
* `2` \(U_i\) \(K_i\) \(S_i\): Print the final node Alphonse will end up at if he:
  - Starts a journey at node \(U_i\).
  - Repeatedly traverses a previously untraversed edge (on this journey). If his current node has multiple untraversed edges, he picks the edge labeled with the letter that comes earliest in the string \(S_i\).
  - Ends the journey once there are no more untraversed edges at the current node, or \(K_i\) edges have been traversed on the journey.

Please help Alphonse determine where each journey will take him.


# Constraints

\(1 \le T \le 20\)
\(2 \le N \le 300{,}000\)
\(1 \le Q \le 300{,}000\)
\(1 \le A_i, B_i \le N\)
\(A_i \ne B_i\)
\(C_i, L_i, S_{i,j} \in \{\)`'A'`, \(\ldots\), `'Z'`\(\}\)
\(1 \le U_i, K_i \le 600{,}000\)

The sum of \(N\) over all test cases is at most \(1{,}100{,}000\).
The sum of \(Q\) over all test cases is at most \(1{,}100{,}000\).

For each event, it is guaranteed that:
- \(U_i\) is a valid node in the tree at the time of the event.
- \(L_i\) is different from all existing labels of edges incident to \(U_i\) at the time of the event.
- \(S_i\)'s letters are distinct, and are a superset of all edge labels in the tree at the time of the event.


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single integer \(N\). Then, \(N - 1\) lines follow, the \(i\)th of which contains space-separated integers \(A_i\) and \(B_i\), followed by a space, followed by \(C_i\). Then, there is a line containing the single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which is either `1` \(U_i\) \(L_i\) or `2` \(U_i\) \(K_i\) \(S_i\).


# Output Format

For the \(i\)th test case, print a single line containing `"Case #i: "`, followed by space-separated integers, the answers to all type-2 events.


# Sample Explanation

{{PHOTO_ID:1175696903384597|WIDTH:550}}

The first sample case's alphabet tree is depicted above, and yields the following journeys:

- Event \(1\) traverses \(1 \stackrel{\texttt{M}}{\longrightarrow} 2 \stackrel{\texttt{E}}{\longrightarrow} 6\) (ended after no more edges from node \(6\))
- Event \(2\) traverses \(3 \stackrel{\texttt{E}}{\longrightarrow} 1 \stackrel{\texttt{T}}{\longrightarrow} 4 \stackrel{\texttt{A}}{\longrightarrow} 9\) (ended after \(K_2 = 3\) steps)
- Event \(3\) traverses \(9 \stackrel{\texttt{A}}{\longrightarrow} 4 \stackrel{\texttt{T}}{\longrightarrow} 1 \stackrel{\texttt{M}}{\longrightarrow} 2\) (ended after \(K_3 = 3\) steps)
- Event \(4\) traverses \(8 \stackrel{\texttt{M}}{\longrightarrow} 3 \stackrel{\texttt{E}}{\longrightarrow} 1 \stackrel{\texttt{T}}{\longrightarrow} 4 \stackrel{\texttt{A}}{\longrightarrow} 9\) (ended after no more edges from node \(9\))
- Event \(6\) traverses \(8 \stackrel{\texttt{T}}{\longrightarrow} 10\) (ended after no more edges from node \(10\))

The second and third sample cases are depicted below.

{{PHOTO_ID:1142476319774543|WIDTH:650}}

In the second case, the journeys are: 

- Event \(1\) traverses \(1 \stackrel{\texttt{P}}{\longrightarrow} 5 \stackrel{\texttt{C}}{\longrightarrow} 2\) (ended after \(K_1 = 2\) steps)
- Event \(2\) traverses \(4 \stackrel{\texttt{P}}{\longrightarrow} 2 \stackrel{\texttt{C}}{\longrightarrow} 5 \stackrel{\texttt{P}}{\longrightarrow} 1\) (ended after \(K_2 = 3\) steps)
- Event \(4\) traverses \(4 \stackrel{\texttt{P}}{\longrightarrow} 2 \stackrel{\texttt{C}}{\longrightarrow} 5 \stackrel{\texttt{U}}{\longrightarrow} 6\) (ended after \(K_4 = 3\) steps)
- Event \(5\) traverses \(3 \stackrel{\texttt{U}}{\longrightarrow} 2 \stackrel{\texttt{P}}{\longrightarrow} 4\) (ended after no more edges from node \(4\))

In the third case, the journeys are: 

- Event \(1\) traverses \(3 \stackrel{\texttt{C}}{\longrightarrow} 2 \stackrel{\texttt{A}}{\longrightarrow} 1\) (ended after \(K_1 = 2\) steps)
- Event \(2\) traverses \(4 \stackrel{\texttt{E}}{\longrightarrow} 2 \stackrel{\texttt{A}}{\longrightarrow} 1\) (ended after \(K_2 = 2\) steps)
- Event \(3\) traverses \(1 \stackrel{\texttt{A}}{\longrightarrow} 2\) (ended after \(K_3 = 1\) steps)


Sample input:
3
9
1 2 M
1 3 E
1 4 T
4 9 A
2 5 T
2 6 E
3 7 A
3 8 M
6
2 1 3 META
2 3 3 TEAM
2 9 3 MATE
2 8 8 TEAM
1 8 T
2 8 8 TEAM
5
1 5 P
5 2 C
2 3 U
4 2 P
5
2 1 2 CPU
2 4 3 CUP
1 5 U
2 4 3 CUP
2 3 4 PUCK
4
2 1 A
2 3 C
4 2 E
3
2 3 2 HACKER
2 4 2 REACH
2 1 1 OCEAN


Sample output:
Case #1: 6 9 2 9 10
Case #2: 2 1 6 4
Case #3: 1 1 2


Solution: The first thing to do is root the tree, for which we can arbitrarily choose node \(1\). Each journey can be done in two phases:
1. *Uplifting*: \(k_1\) steps in root's direction (\(k_1\) can be zero).
2. *Descent*: \(k_2\) steps in the opposite direction (\(k_2\) can be zero, \(k_1 + k_2 \le K_i\)).

Indeed, after we descend one step, there is no way to start moving up, because the previous edge will always be the edge we need to go upwards (and we can't traverse an edge twice).

Next, notice that adding new nodes don't make the problem significantly harder. We can preprocess all type-1 events and construct the full tree, then process events of both types in reverse order: it's easier to remove nodes rather than to add them. For a reverse type-1 event, we'll replace the node with a reference to its parent so that whenever we get to this node, we instantly return to its parent. For some removals, we must repeat until we reached a node that still exists in the tree. A disjoint set union (DSU) data structure can be used to perform these operations efficiently. For each node, we'll use DSU to find the bottommost ancestor that still exists in the tree.

Now, we'll need a way to perform phase 1 and phase 2 in time faster than \(\mathcal{O}(N + Q)\). For simplicity, we'll describe the solution for an indefinite \(K\). If the destination node is known, we can always backtrack a certain number of steps using binary lifting.

*Phase 1.* In this problem, we have an radix size of \(R = 26\), so we have only \(26 * 25 = 650\) unique pairs of letters. Let's call a pair of letters \((c_1, c_2)\) *active* if \(c_1\) precedes \(c_2\) in the given string \(S_i\). For each edge and pair of letters, we can precompute the ancestor node where the uplifting ends (due to this pair being active) using depth-first search in \(\mathcal{O}((N + Q) * R^2)\). If we start at some node \(v\) and we need to find the node where uplifting stops, we should do the following:

1. Start uplifting at node \(v\). Look through all the edges adjacent to \(v\) to make sure the first edge of the traversal will be the edge to its parent. If not, there is no uplifting for the current event.
2. Iterate over all active pairs and pick the bottommost precomputed node across all these pairs for the edge from node \(v\) to its parent. This node is the destination of uplifting.

The total complexity for phase 1 of a single journey is \(\mathcal{O}(R^2)\). We only iterate over at most \(R\) edges and over at most \(R * (R - 1) / 2\) pairs.

*Phase 2.* This phase is slightly more difficult because we have to pick the right edge by ourselves (where in phase 1, we always took the edge from a node to its parent). One possible strategy is to consider the edge that leads to the largest subtree. For each node and pair of letters, we can precompute the descendant node where the descent ends due to this pair being active. The way we use this data is very similar to phase 1:

1. Start the descent at node \(v\).
2. Iterate over all active pairs and pick the topmost precomputed node \(u\) across all these pairs for the vertex \(v\). It's possible that \(u = v\).
3. Look through all edges adjacent to \(u\) for the next step. If there is no such edge, node \(u\) is the destination of our descent. Otherwise, this edge leads to the node we assign to \(v\), and we return to step 2.

Each time we perform step 3, we reduce the maximum possible number of steps left by at least a half, so at most we will repeat it \(\mathcal{O}(\log(N + Q))\) times for each journey. Since each such step takes \(\mathcal{O}(R^2)\) time, the overall time complexity for phase 2 of a journey is \(\mathcal{O}(\log(N + Q) * R^2)\), and the overall time complexity is therefore \(\mathcal{O}(Q * \log(N + Q) * R^2)\).



Code: #include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

using pii = pair<int, int>;

struct Req {
  int ind, t, x, y;
  vector<int> alph;
};

int pair_cnt;
vector<vector<int>> pair_map;

int N, M, Q;
vector<pii> edges;
vector<vector<pii>> g;
vector<Req> a;
vector<int> ans, lnks, lnks_z, lnk_jump, d, par, par_z;
vector<vector<int>> top_links, bot_links, bu_links;

vector<int> dsu;

int get_dsu_parent(int x) {
  if (dsu[x] == dsu[dsu[x]]) {
    return dsu[x];
  }
  return dsu[x] = get_dsu_parent(dsu[x]);
}

int get_top_link(int edge_ind, int pair_ind) {
  if (top_links[edge_ind][pair_ind] == edge_ind) {
    return edge_ind;
  }
  return get_top_link(top_links[edge_ind][pair_ind], pair_ind);
}

int get_edge_ind(int x, int y) {
  pii edge(x, y);
  int l = 0, r = M - 1;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (edges[mid] == edge) {
      return mid;
    }
    if (edges[mid] < edge) {
      l = mid + 1;
    } else {
      r = mid - 1;
    }
  }
  return -1;
}

void precalc() {
  pair_map.assign(26, vector<int>(26, -1));
  pair_cnt = 0;
  for (int z1 = 0; z1 < 26; z1++) {
    for (int z2 = z1 + 1; z2 < 26; z2++) {
      pair_map[z1][z2] = pair_cnt++;
      pair_map[z2][z1] = pair_cnt++;
    }
  }
}

void add_edge(int x, int y, int z) {
  edges.push_back({x, y});
  g[x].push_back({y, z});
}

int dfs_lnks(int x, int p) {
  par[x] = p;
  lnk_jump[x] = x;
  if (x == p) {
    d[x] = 0;
  } else {
    d[x] = d[p] + 1;
  }
  lnks[x] = -1;
  lnks_z[x] = -1;
  int best = 0, total = 0;
  for (auto [y, z] : g[x]) {
    if (y == p) {
      par_z[x] = z;
      continue;
    }
    int cur = dfs_lnks(y, x);
    total += cur;
    if (cur > best) {
      best = cur;
      lnk_jump[x] = lnk_jump[y];
      lnks[x] = y;
      lnks_z[x] = z;
    }
  }
  return total + 1;
}

void run_precalc_top(int x, int p) {
  if (x != p) {
    int edge_ind = get_edge_ind(x, p);
    if (p == par[p]) {
      top_links[edge_ind].assign(pair_cnt, edge_ind);
    } else {
      int par_edge_ind = get_edge_ind(p, par[p]);
      top_links[edge_ind] = top_links[par_edge_ind];
    }

    if (par[p] != p) {
      int ppz = par_z[p];
      for (auto [y, z] : g[p]) {
        if (y == par[p] || y == x) {
          continue;
        }
        top_links[edge_ind][pair_map[z][ppz]] = edge_ind;
      }
    }
  }
  for (int i = 0; i < (int)g[x].size(); i++) {
    int y = g[x][i].first;
    if (y == p) {
      continue;
    }
    run_precalc_top(y, x);
  }
}

void run_precalc_bot(int x, int p) {
  for (auto [y, _] : g[x]) {
    if (y != p) {
      run_precalc_bot(y, x);
    }
  }
  int ly = lnks[x], lz = lnks_z[x];
  if (ly != -1) {
    bot_links[x] = bot_links[ly];
    for (auto [y, z] : g[x]) {
      if (y == ly || y == p) {
        continue;
      }
      bot_links[x][pair_map[z][lz]] = x;
    }
  } else {
    bot_links[x].assign(pair_cnt, x);
  }
}

void binary_uplifting() {
  int sz = (int)g.size();
  int maxp = 1;
  while ((1 << maxp) < sz) {
    ++maxp;
  }
  ++maxp;
  bu_links.assign(maxp, vector<int>(sz));
  for (int i = 0; i < sz; i++) {
    bu_links[0][i] = par[i];
  }
  for (int p = 1; p < maxp; p++) {
    for (int i = 0; i < sz; i++) {
      bu_links[p][i] = bu_links[p - 1][bu_links[p - 1][i]];
    }
  }
}

void init() {
  int x = 0, y = 0, z = 0;
  char c = 0;
  g.clear();
  edges.clear();
  edges.reserve(N << 2);
  cin >> N;
  g.resize(N);
  for (int i = 1; i < N; i++) {
    cin >> x >> y >> c;
    --x, --y;
    z = (int)(c - 'A');
    add_edge(x, y, z);
    add_edge(y, x, z);
  }
  int t = 0;
  string s;
  vector<int> alph;
  cin >> Q;
  a.resize(Q);
  for (int i = 0; i < Q; i++) {
    Req &r = a[i];
    cin >> t;
    --t;
    r.ind = i;
    r.t = t;
    if (t) {
      cin >> x >> y >> s;
      --x;
      alph.resize(s.length());
      for (int i = 0; i < (int)s.length(); i++) {
        alph[i] = (int)(s[i] - 'A');
      }
      r.x = x;
      r.y = y;
      r.alph = alph;
    } else {
      y = (int)(g.size());
      g.push_back({});
      cin >> x >> c;
      --x;
      z = (int)(c - 'A');
      add_edge(x, y, z);
      add_edge(y, x, z);
      r.x = x;
      r.y = y;
    }
  }
  sort(edges.begin(), edges.end());
  M = edges.size();
  top_links.resize(M);

  dsu.resize(g.size());
  for (int i = 0; i < (int)g.size(); i++) {
    dsu[i] = i;
  }

  par.resize(g.size());
  par_z.resize(g.size());
  d.resize(g.size());
  lnks.resize(g.size());
  lnks_z.resize(g.size());
  lnk_jump.resize(g.size());

  bot_links.resize(g.size());
  dfs_lnks(0, 0);
  binary_uplifting();
  run_precalc_top(0, 0);
  run_precalc_bot(0, 0);
}

int get_uplift(int x, int k) {
  for (int p = (int)bu_links.size() - 1; p >= 0; --p) {
    if (k & (1 << p)) {
      x = bu_links[p][x];
    }
  }
  return x;
}

int go_up(int x, int &k, const vector<int> &stop_vector) {
  int p = par[x];
  if (x == p) {
    return x;
  }
  int edge_ind = get_edge_ind(x, p), y = 0;
  for (int _y : stop_vector) {
    int ny = edges[get_top_link(edge_ind, _y)].second;
    if (d[y] < d[ny]) {
      y = ny;
    }
  }
  int dif = d[x] - d[y];
  if (k < dif) {
    y = get_uplift(x, k);
    k = 0;
  } else {
    k -= dif;
  }
  return y;
}

int go_down(int x, int &k, const vector<int> &stop_vector,
            const vector<int> &rev_alph) {
  while (k) {
    if (lnks[x] == -1) {
      break;
    }
    int y = lnk_jump[x];
    for (int _y : stop_vector) {
      int ny = bot_links[x][_y];
      if (d[y] > d[ny]) {
        y = ny;
      }
    }
    y = get_dsu_parent(y);
    int dif = d[y] - d[x];
    if (k < dif) {
      y = get_uplift(y, dif - k);
      k = 0;
    } else {
      k -= dif;
    }
    if (k) {
      int ny = -1, nz = 26;
      for (auto [yy, _zz] : g[y]) {
        if (yy == par[y] || yy != dsu[yy]) {
          continue;
        }
        int zz = rev_alph[_zz];
        if (nz > zz) {
          nz = zz;
          ny = yy;
        }
      }
      if (ny == -1) {
        x = y;
        break;
      }
      --k;
      y = ny;
    }
    x = y;
  }
  return x;
}

int get_res(int x, int k, const vector<int> &alph) {
  if (!k) {
    return x;
  }
  vector<int> stop_vector;
  for (int i = 0; i < (int)alph.size(); i++) {
    for (int j = i + 1; j < (int)alph.size(); j++) {
      stop_vector.push_back(pair_map[alph[i]][alph[j]]);
    }
  }
  vector<int> rev_alph(26, -1);
  for (int i = 0; i < (int)alph.size(); i++) {
    rev_alph[alph[i]] = i;
  }
  if (x != par[x]) {
    int up_dir = 1;
    for (auto [y, z] : g[x]) {
      if (y == par[x] || y != dsu[y]) {
        continue;
      }
      if (rev_alph[par_z[x]] > rev_alph[z]) {
        up_dir = 0;
        break;
      }
    }
    if (up_dir) {
      int pk = k, px = x;
      x = go_up(x, k, stop_vector);
      if (k) {
        int nx = get_uplift(px, pk - k - 1);
        int y = -1, z = 26;
        for (auto [ny, _nz] : g[x]) {
          if (ny == par[x] || ny == nx || ny != dsu[ny]) {
            continue;
          }
          int nz = rev_alph[_nz];
          if (nz < z) {
            y = ny;
            z = nz;
          }
        }
        if (y == -1) {
          return x;
        }
        x = y;
        --k;
      }
    }
  }
  if (k) {
    x = go_down(x, k, stop_vector, rev_alph);
  }
  return x;
}

void update_precalc_top(int x) {
  int p = par[x];
  if (x == p || p == par[p]) {
    return;
  }
  int par_edge_ind = get_edge_ind(p, par[p]);
  int ppz = par_z[p], z = -1;
  for (auto [y, _z] : g[p]) {
    if (y != x) {
      continue;
    }
    z = _z;
    break;
  }
  for (auto [y, _z] : g[p]) {
    if (y == par[p] || y != dsu[y]) {
      continue;
    }
    int edge_ind = get_edge_ind(y, p);
    int pair_ind = pair_map[z][ppz];
    top_links[edge_ind][pair_ind] = get_top_link(par_edge_ind, pair_ind);
  }
}

void solve() {
  ans.assign(Q, -1);
  for (int i = Q - 1; i >= 0; --i) {
    const Req &req = a[i];
    if (req.t) {
      ans[req.ind] = get_res(req.x, req.y, req.alph);
    } else {
      dsu[req.y] = get_dsu_parent(par[req.y]);
      update_precalc_top(req.y);
    }
  }
  for (int i = 0; i < Q; i++) {
    if (ans[i] != -1) {
      cout << " " << ans[i] + 1;
    }
  }
  cout << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  precalc();
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    init();
    cout << "Case #" << t << ":";
    solve();
  }
  return 0;
}