Language: C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>

using namespace std;

struct Edge {
  int to;
  int color;
  int length;
};
struct Node {
  int i;
  vector<Edge> neighbors;
  int parent;
  int depth;
  int dist; // ルートからの距離
  int route_order; // 通りがかった順
};
struct ColorEdge {
  int to_route_order;
  int count;
  int sum_length;

  // 2分探索用に定義
  bool operator<(const ColorEdge& other) const
  {
     return (to_route_order < other.to_route_order);
  }
  bool operator>(const ColorEdge& other) const
  {
     return (to_route_order > other.to_route_order);
  }
  bool operator==(const ColorEdge& other) const
  {
     return (to_route_order == other.to_route_order);
  }
};

vector<Node> nodes;
vector<vector<int>> ancestors_cache;
vector<vector<ColorEdge>> color_edges;
int route_order_index = 0;

// 祖先探索
// 2の累乗についてはキャッシュ化する
int ancestor(int current, int generation) {
  if (generation <= 0) {
    return current;
  }

  if (generation == 1) {
    return nodes[current].parent;
  }

  float near_2_pow = pow(2, floor(log2(generation)));
  // cout << "near_2_pow " << near_2_pow << endl;
  if (near_2_pow == generation) {
    //generation=0,1はスキップされるので、[0]がgeneration=2に相当
    int ancestors_cache_i = floor(log2(generation)) - 1;

    if (ancestors_cache[current][ancestors_cache_i] == -1) {
      ancestors_cache[current][ancestors_cache_i] =
          ancestor(ancestor(current, generation/2), generation/2);
    }

    return ancestors_cache[current][ancestors_cache_i];
  } else {
    return ancestor(ancestor(current, near_2_pow), generation - near_2_pow);
  }
}

// 共通の一番近い祖先探索
int shared_neareast_ancestor(int a, int b) {
  Node na,nb;
  na = nodes[a];
  nb = nodes[b];

  if (na.depth > nb.depth) {
    a = ancestor(a, na.depth - nb.depth);
  } else if (na.depth < nb.depth) {
    b = ancestor(b, nb.depth - na.depth);
  }

  if (a == b) {
    return a;
  }

  int a_ancestor, b_ancestor;
  for (int i = floor(log2(nodes[a].depth)); i > 0; i--) {
    a_ancestor = ancestor(a, i);
    b_ancestor = ancestor(b, i);

    if (a_ancestor != b_ancestor) {
      a = a_ancestor;
      b = b_ancestor;
    }
  }

  return na.parent;
}

// 越えない最大値を探す
ColorEdge get_max_index(vector<ColorEdge> ce, int route_order) {
  auto ite = upper_bound(ce.begin(), ce.end(), ColorEdge{route_order}); //upper_boundは超える最小の要素を探す
  auto index = distance(ce.begin(), ite);
  return ce[index - 1]; //ので、一個前を返す。0があるので、要素がないことはない
}

void dfs(int current, int before, int depth, int dist, Edge* e) {
  int color_edges_count, color_edges_sum_length;

  nodes[current].parent = before;
  nodes[current].depth = depth;
  nodes[current].dist = dist;
  ancestors_cache[current].assign(depth <= 1 ? 0 : floor(log2(depth)), -1);
  nodes[current].route_order = route_order_index++;
  
  if (e != nullptr) {
    // 到達したときに、色の履歴を追加
    color_edges_count = color_edges[e->color].back().count + 1;
    color_edges_sum_length = color_edges[e->color].back().sum_length + e->length;
    color_edges[e->color].push_back(
      {nodes[current].route_order, color_edges_count, color_edges_sum_length});
  }

  for (Edge new_e : nodes[current].neighbors) {
    if (new_e.to == before) {
      continue;
    }

    dfs(new_e.to, current, depth+1, dist+new_e.length, &new_e);
    
    // 戻ってきたときに、色の履歴(マイナス)を追加
    color_edges[new_e.color].push_back(
      {route_order_index++,
      color_edges[new_e.color].back().count - 1,
      color_edges[new_e.color].back().sum_length - new_e.length});
  }
}

int main() {
  int n,q,a,b,c,d,x,y,u,v;
  cin >> n;
  cin >> q;

  // node設定
  for (int i = 0; i <= n; i++) {
    nodes.push_back({i, {}});
  }
  for (int i = 0; i < n - 1; i++) {
    cin >> a;
    cin >> b;
    cin >> c;
    cin >> d;
    nodes[a].neighbors.push_back({b,c,d});
    nodes[b].neighbors.push_back({a,c,d});
  }

  // 探索して各データ作成
  ancestors_cache.assign(n+1, vector<int>{});
  for (int i = 0; i < n; i++) {
    color_edges.push_back(vector<ColorEdge>{{route_order_index, 0, 0}});
  }
  dfs(1, -1, 0, 0, nullptr);

  // colorをcolor_edgesとroute_orderから探索する
  int result;
  for (int i = 0; i < q; i++) {
    cin >> x;
    cin >> y;
    cin >> u;
    cin >> v;

    Node nu = nodes[u];
    Node nv = nodes[v];
    int sa = shared_neareast_ancestor(u, v);
    result = 0;

    // まず、色を考慮しない距離を出す。uまで+xまで-共通部分*2
    result += nu.dist;
    result += nv.dist;
    result -= nodes[sa].dist * 2;

    // 色付き辺を探す
    int f = min(nu.route_order, nv.route_order);
    int t = max(nu.route_order, nv.route_order);
    vector<ColorEdge>* ce = &(color_edges[x]);

    // 空間削減のため、変化したときのみデータ記録しているので、
    // 2分探索して探す
    ColorEdge share_ancestor_order_route = get_max_index(ce, nodes[sa].route_order);
    /*
    ColorEdge from_order_route = get_max_index(ce, f);
    ColorEdge to_order_route = get_max_index(ce, t);

    // 計算はdistと同じく、uまで+xまで-共通部分*2
    int count = (to_order_route).count + (from_order_route).count - 2 * (share_ancestor_order_route).count;
    int sum_length = (to_order_route).sum_length + (from_order_route).sum_length - 2 * (share_ancestor_order_route).sum_length;
    result = result - sum_length + (count * y);
  */  
    cout << result << endl;
    
    if (i >= 1000) {
    	break;
    }
  }

  /* debug
  cout << "nodes (parent,depth,dist,route_order)" << endl;
  for (Node n : nodes) {
    cout << n.i << " ";
    cout << n.parent << " ";
    cout << n.depth << " ";
    cout << n.dist << " ";
    cout << n.route_order << " ";
    cout << endl;
  }

  cout << ancestor(5, 1) << endl;
  cout << ancestor(2, 1) << endl;
  cout << ancestor(5, 2) << endl;
  cout << ancestor(4, 1) << endl;
  cout << ancestor(4, 2) << endl;
  cout << shared_neareast_ancestor(5, 4) << endl;
  cout << shared_neareast_ancestor(1, 4) << endl;
  cout << shared_neareast_ancestor(3, 4) << endl;

  cout << "ancestors_cache" << endl;
  for (vector<int> i : ancestors_cache) {
    for (int j : i) {
      cout << j << " ";
    }
    cout << endl;
  }

  for (int i = 0; i < n; i++) {
    for (ColorEdge ce : color_edges[i]) {
      cout << i << " " << ce.to_route_order <<
        " " << ce.count << " " << ce.sum_length << endl;
    }
  }
  */

  return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:194:58: error: could not convert 'ce' from 'std::vector<ColorEdge>*' to 'std::vector<ColorEdge>'
  194 |     ColorEdge share_ancestor_order_route = get_max_index(ce, nodes[sa].route_order);
      |                                                          ^~
      |                                                          |
      |                                                          std::vector<ColorEdge>*