Language: C++

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
ll MOD = 1000000007LL;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

inline ll floor(ll a, ull b)
{
	ll llb = b;
	if (a >= 0)
	{
		return a / llb;
	}
	else
	{
		return - ( (-a + llb - 1) / llb);
	}
}

inline ll ceil(ll a, ull b)
{
	ll llb = b;
	if (a >= 0)
	{
		return (a + llb - 1) / llb;
	}
	else
	{
		return - (-a / llb);
	}
}

inline ll get_lowest_one_bit(ll a)
{
	return a & (-a);
}

inline ll get_highest_one_bit(ll a)
{
	while ((a & (a - 1)) != 0)
	{
		a = a & (a - 1);
	}
	return a;
}

inline bool is_power2(ull a)
{
	if (a == 0)
	{
		return false;
	}
	return !(a & (a - 1));
}

inline ll get_specified_bit(ll a, unsigned bit)
{
	return (a & (1LL << bit)) >> bit;
}

// computational complexity: o(log(max(a, b))) 
inline ull get_gcd(ull a, ull b)
{
	if (b == 0)
	{
		return a;
	}
	return get_gcd(b, a % b);
}

template<class Integer>
inline Integer get_power(Integer base, ull exponential)
{
	Integer result = 1;
	while (exponential >= 1)
	{
		if (exponential & 1)
		{
			result = result * base;
		}
		base = base * base;
		exponential >>= 1;
	}

	return result;
}

using Edge = pair<ll, ll>;

struct Graph
{
	using Vertex = ll;
	ll vertex_count;
	vector<Edge> edges;
	
	Graph() : vertex_count(0LL), edges(0LL) {}
	Graph(ll vertex_count) : vertex_count(vertex_count), edges(0LL) {}

	void add_edge(const Edge& edge)
	{
		edges.emplace_back(edge);
	}

	vector<vector<tuple<Vertex, Vertex>>> get_adjacency_list() const
	{
		using EdgeWithInfo = tuple<Vertex, Vertex>;
		// 辺の隣接リストを作成
		vector<vector<EdgeWithInfo>> adjancency_list(vertex_count);
		for (ll i = 0; i < edges.size(); ++i)
		{
			Vertex from, to;
			tie(from, to) = edges[i];
			adjancency_list[from].emplace_back(from, to);
		}
		return move(adjancency_list);
	}
	
	template<class EdgeInfo>
	vector<vector<tuple<Vertex, Vertex, EdgeInfo>>> get_adjacency_list(const vector<EdgeInfo>& infos) const
	{
		using EdgeWithInfo = tuple<Vertex, Vertex, EdgeInfo>;
		// 辺の隣接リストを作成
		vector<vector<EdgeWithInfo>> adjancency_list(vertex_count);
		for (ll i = 0; i < edges.size(); ++i)
		{
			Vertex from, to;
			tie(from, to) = edges[i];
			const EdgeInfo& info = infos[i];
			adjancency_list[from].emplace_back(from, to, info);
		}
		return move(adjancency_list);
	}
};

template<class EdgeInfo>
pair<Graph, vector<EdgeInfo>> get_rooted_bfs_tree_graph(const Graph& graph, vector<EdgeInfo>& infos, ll r = 0LL)
{
	Graph rooted_tree(graph.vertex_count);
	auto adjacency_list = graph.get_adjacency_list(infos);

	vector<EdgeInfo> new_infos;

	queue<ll> queue;
	vector<bool> have_checked(graph.vertex_count);

	queue.push(r);
	have_checked[r] = true;
	while (!queue.empty())
	{
		ll from = queue.front();
		queue.pop();
		for (auto& edge : adjacency_list[from])
		{
			ll to;
			EdgeInfo info;
			tie(from, to, info) = edge;
			if(have_checked[to])
				continue;
			rooted_tree.add_edge({ from, to });
			new_infos.emplace_back(info);
			queue.push(to);
			have_checked[to] = true;
		}
	}

	return {rooted_tree, new_infos};
}

class TreeLCACalculator
{
private:
	vector<vector<ll>> parent_by_power2;
	vector<ll> depths;
public:
	TreeLCACalculator(ll node_count, const vector<vector<ll>>& edges, ll s = 0LL) :
		parent_by_power2(node_count), depths(node_count)
	{
		vector<bool> have_checked(node_count, false);
		queue<ll> queue;

		queue.emplace(s);
		depths[s] = 0;
		parent_by_power2[s] = { s };
		have_checked[s] = true;

		while (!queue.empty())
		{
			ll from = queue.front();
			queue.pop();

			for (auto& to : edges[from])
			{
				if (have_checked[to])
					continue;

				depths[to] = depths[from] + 1;
				parent_by_power2.reserve(parent_by_power2[from].size() + 1LL);
				parent_by_power2[to].emplace_back(from);
				copy(parent_by_power2[from].begin(), parent_by_power2[from].end(), back_inserter(parent_by_power2[to]));
				queue.push(to);
				have_checked[to] = true;
			}
		}
	}

	ll calculate(ll node1, ll node2) {
		if (depths[node1] < depths[node2])
		{
			auto tmp = node1;
			node1 = node2;
			node2 = tmp;
		}
		if (depths[node1] > depths[node2])
		{
			auto diff = depths[node1] - depths[node2];
			while (diff > 0)
			{
				node1 = parent_by_power2[node1][get_highest_one_bit(diff & -diff)];
				diff -= diff & -diff;
			}
		}

		if (node1 == node2)
			return node1;

		const ll sz = parent_by_power2[node1].size();
		for (ll i = 0; i < sz; ++i)
		{
			if (parent_by_power2[node1][sz - i - 1] != parent_by_power2[node2][sz - i - 1])
			{
				node1 = parent_by_power2[node1][sz - i - 1];
				node2 = parent_by_power2[node2][sz - i - 1];
			}
		}

		return parent_by_power2[node1][0];
	}
};

template<class EdgeInfo>
pair<vector<pair<tuple<ll, ll, EdgeInfo>, string>>, vector<pair<ll, ll>>>
get_euler_tour(const Graph& rooted_tree, const vector<EdgeInfo>& edge_infos, ll r)
{
	using Vertex = ll;
	using EdgeWithInfo = tuple<Vertex, Vertex, EdgeInfo>;
	auto adjacent_list = rooted_tree.get_adjacency_list(edge_infos);

	// DFS
	struct EulerTourCalculator
	{
		const vector<vector<EdgeWithInfo>> adjacency_list;
		vector<bool> have_checked;
		vector<EdgeWithInfo> prev_edges;
		vector<pair<EdgeWithInfo, string>> euler_tour;

		EulerTourCalculator(const vector<vector<EdgeWithInfo>>& adjacency_list, ll r) :
			adjacency_list(adjacency_list),
			have_checked(adjacency_list.size(), false),
			prev_edges(adjacency_list.size())
		{
			have_checked[r] = true;
			get<0>(prev_edges[r]) = -1LL;
			get<1>(prev_edges[r]) = r;
			call(r);
		}

		void call(ll from)
		{
			for (const auto& edge : adjacency_list[from])
			{
				ll to = get<1>(edge);

				if (have_checked[to])
					continue;

				have_checked[to] = true;
				prev_edges[to] = edge;
				euler_tour.emplace_back(edge, "+");
				call(to);
			}
			euler_tour.emplace_back(prev_edges[from], "-");
		}
	};

	auto euler_tour = EulerTourCalculator(adjacent_list, r).euler_tour;

	vector<pair<ll, ll>> tour_index(rooted_tree.vertex_count, { -1, -1 });
	tour_index[r].first = 0LL;
	for (ll i = 0; i < euler_tour.size(); ++i)
	{
		EdgeWithInfo edge;
		string type;
		tie(edge, type) = euler_tour[i];
		ll from = get<0>(edge), to = get<1>(edge);

		if (type == "+" && tour_index[to].first == -1)
		{
			tour_index[to].first = i + 1;
		}
		else if (type == "-" && tour_index[to].second == -1)
		{
			tour_index[to].second = i;
		}
	}

	return { euler_tour, tour_index };
}

// 始点 s から各点への最短距離を返します。
// パス自体が存在しない場合は -1 を返します。
// 距離 lengths の各要素は非負である必要があります。
pair<vector<ll>, vector<ll>> dijkstra(const Graph& graph, const vector<ll>& lengths, ll s = 0LL)
{
	using Vertex = ll;
	using Length = ll;
	struct _Edge
	{
		Vertex from, to;
		Length length;
		_Edge() : from(-1LL), to(-1LL), length(0LL) {}
		_Edge(Vertex from, Vertex to, Length length) :
			from(from), to(to), length(length) {}
	};

	if (graph.edges.size() != lengths.size())
		throw runtime_error("グラフの辺の要素数と辺の長さの要素数は一致している必要があります。");

	// 辺の隣接リストを作成
	vector<vector<_Edge>> edges(graph.vertex_count);
	for (ll i = 0; i < graph.edges.size(); ++i)
	{
		Vertex from, to;
		tie(from, to) = graph.edges[i];
		Length length = lengths[i];
		if (length < 0)
			throw runtime_error("グラフの辺の長さは非負である必要があります。");

		edges[from].emplace_back(from, to, length);
	}

	// アルゴリズム本体
	using VertexInfo = pair<Length, Vertex>;
	priority_queue<VertexInfo, vector<VertexInfo>, greater<VertexInfo>> queue;
	vector<Length> dists(graph.vertex_count, 1LL << 60);
	vector<Vertex> prev_vertices(graph.vertex_count, -1LL);

	dists[s] = 0LL;
	queue.emplace(dists[s], s);
	prev_vertices[s] = s;
	while (!queue.empty())
	{
		Length l;
		Vertex v;
		tie(l, v) = queue.top();
		queue.pop();
		if (dists[v] < l) continue;
		for (auto& edge : edges[v])
		{
			Vertex to = edge.to;
			if (dists[to] > dists[v] + edge.length)
			{
				dists[to] = dists[v] + edge.length;
				queue.emplace(dists[to], to);
				prev_vertices[to] = v;
			}
		}
	}
	for (ll i = 0; i < graph.vertex_count; ++i)
	{
		if (prev_vertices[i] == -1LL)
			dists[i] = -1LL;
	}

	return { dists, prev_vertices };
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	using Info = pair<ll, ll>;

	ll N, Q;
	cin >> N >> Q;

	vector<vector<ll>> edges(N);
	Graph g(N);
	vector<ll> lengths;
	vector<Info> infos;
	ll a, b, c, d;
	for (ll i = 0; i < N - 1; ++i)
	{
		cin >> a >> b >> c >> d;
		--a, --b;
		edges[a].emplace_back(b);
		edges[b].emplace_back(a);

		g.add_edge({ a, b });
		g.add_edge({ b, a });
		infos.emplace_back(c, d);
		infos.emplace_back(c, d);
		lengths.emplace_back(d);
		lengths.emplace_back(d);
	}

	ll root = 0LL;

	auto dists = dijkstra(g, lengths, root).first;
	TreeLCACalculator calc(N, edges, root);

	Graph rooted_tree;
	tie(rooted_tree, infos) = get_rooted_bfs_tree_graph(g, infos);

	auto tour_info = get_euler_tour(rooted_tree, infos, root);
	auto euler_tour = tour_info.first;
	auto tour_index = tour_info.second;

	map<pair<ll, ll>, pair<ll, ll>> color_map;
	for (ll i = 0; i < euler_tour.size(); ++i)
	{
		const auto& tour_edge = euler_tour[i];
		ll from, to, color, length;
		string type;
		tie(tie(from, to, tie(color, length)), type) = tour_edge;

		auto iter = color_map.lower_bound({ color, i + 1 });
		ll color_count = 1LL;
		if (iter != color_map.begin())
		{
			--iter;
			if (iter->first.first == color)
			{
				color_count = iter->second.first + color_count * (type == "+" ? 1LL : -1LL);
				length = iter->second.second + length * (type == "+" ? 1LL : -1LL);
			}
		}
		color_map[{color, i + 1}] = {color_count, length};
	}

	ll x, y, u, v, w;
	for (ll i = 0; i < Q; ++i)
	{
		cin >> x >> y >> u >> v;
		--u, --v;
		w = calc.calculate(u, v);

		auto dist = dists[u] + dists[v] - dists[w] * 2;
		auto u_index = tour_index[u].first;
		auto v_index = tour_index[v].first;

		{
			ll length = 0, color_count = 0;
			auto iter = color_map.upper_bound({ x, u_index });
			if (iter != color_map.begin())
			{
				--iter;
				if (iter->first.first == x)
				{
					color_count = iter->second.first;
					length = iter->second.second;
				}
			}
			dist = dist - length + y * color_count;
		}

		{
			ll length = 0, color_count = 0;
			auto iter = color_map.upper_bound({ x, v_index });
			if (iter != color_map.begin())
			{
				--iter;
				if (iter->first.first == x)
				{
					color_count = iter->second.first;
					length = iter->second.second;
				}
			}
			dist = dist - length + y * color_count;
		}
		cout << dist << endl;
	}

	return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:463:38: error: cannot bind non-const lvalue reference of type 'std::tuple<long long int&, long long int&>&' to an rvalue of type 'std::tuple<long long int&, long long int&>'
  463 |                 tie(tie(from, to, tie(color, length)), type) = tour_edge;
      |                                   ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/vector:87,
                 from a.cc:3:
/usr/include/c++/14/tuple:2791:19: note:   initializing argument 3 of 'constexpr std::tuple<_Elements& ...> std::tie(_Elements& ...) [with _Elements = {long long int, long long int, tuple<long long int&, long long int&>}]'
 2791 |     tie(_Elements&... __args) noexcept
      |         ~~~~~~~~~~^~~~~~~~~~