Language: C++

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

//const long long int MOD = 1000000007;
const int MOD = 1000000007;
//const int MOD = 998244353;
//const long long int MOD = 998244353;
const double EPS = 1e-8;
const int MAX = 600;

int N, M, K, H, W, L, R;
//long long int N, M, K, H, W, L, R;

struct Edge {
	int to, color, cost;
	Edge(int c, int e, int f) {
		to = c, color = e, cost = f;
	}
};


class Lowest_Common_Ancestor {
	vector<vector<int>>parent;
	vector<vector<int>>edge;
	int height = 0;
	int node;
public:
	vector<int>depth;
	Lowest_Common_Ancestor(int num) {
		num++;
		node = num;
		while (num) {
			height++;
			num /= 2;
		}
		parent.resize(height);
		edge.resize(node);
		depth.resize(node);
		for (int i = 0; i < height; i++)parent[i].resize(node);
	}
	void Add_Edge(int a, int b) {
		edge[a].push_back(b);
		edge[b].push_back(a);
		return;
	}
	void Update(int rtnode) {
		queue<int>QQ;
		for (int i = 0; i < node; i++) depth[i] = INT_MAX;
		depth[rtnode] = 0;
		QQ.push(rtnode);
		while (!QQ.empty()) {
			int c = QQ.front();
			for (auto i : edge[c]) {
				if (depth[i] > depth[c] + 1) {
					depth[i] = depth[c] + 1;
					QQ.push(i);
				}
			}
			QQ.pop();
		}
		parent[0][rtnode] = -1;
		for (int i = 1; i < node; i++) {
			for (auto j : edge[i]) {
				if (depth[i] - 1 == depth[j]) {
					parent[0][i] = j;
					break;
				}
			}
		}
		for (int i = 0; i < height - 1; i++) {
			for (int j = 0; j < node; j++) {
				if (parent[i][j] < 0)parent[i + 1][j] = -1;
				else parent[i + 1][j] = parent[i][parent[i][j]];
			}
		}
		return;
	}
	inline int LCA(int u, int v) {
		if (depth[u] > depth[v])swap(u, v);
		for (int i = 0; i < height; i++) {
			if ((depth[v] - depth[u]) >> i & 1) {
				v = parent[i][v];
				if (depth[v] == depth[u])break;
			}
		}
		if (u == v)return u;
		for (int i = height - 1; i >= 0; i--) {
			if (parent[i][v] != parent[i][u]) {
				u = parent[i][u];
				v = parent[i][v];
			}
		}
		return parent[0][u];
	}
	int Dist(int u, int v) {
		return depth[u] + depth[v] - depth[LCA(u, v)] * 2;
	}
};

struct CEdge {
	int from, to, color, cost;
	CEdge(int a, int b, int c, int d) {
		from = a, to = b, color = c, cost = d;
	}
};

struct Query {
	int color, cost, l, r;
	Query(int a, int b, int c, int d) {
		color = a, cost = b, l = c, r = d;
	}
};

int num[MAX][100000];
int dis[MAX][100000];
int converter[100000];
int all_dis[100000];

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

	cin >> N >> K;
	for (int i = 0; i < N; i++)converter[i] = -1;
	vector<pair<int, int>>e_num(N - 1);
	vector<vector<Edge>>edge(N);
	vector<vector<CEdge>>cedge(N);
	Lowest_Common_Ancestor lca(N);
	for (int i = 1; i < N; i++) {
		cin >> L >> R >> H >> W;
		L--, R--, H--;
		lca.Add_Edge(L, R);
		e_num[H].first++;
		edge[L].push_back(Edge(R, H, W));
		edge[R].push_back(Edge(L, H, W));
	}
	vector<Query>q;
	vector<int>qnum(N);
	while (K--) {
		cin >> H >> W >> L >> R;
		qnum[H - 1]++;
		q.push_back(Query(H, W, L, R));
	}
	lca.Update(0);
	for (int i = 0; i < N; i++) {
		for (auto j : edge[i]) {
			if (lca.depth[i] < lca.depth[j.to]) {
				cedge[j.color].push_back(CEdge(i, j.to, j.color, j.cost));
			}
		}
	}
	for (int i = 0; i < N; i++) {
		e_num[i].second = i;
		e_num[i].first *= qnum[i];
	}
	int cn;
	queue<int>Q;
	sort(e_num.begin(), e_num.end(),greater<int>());
	for (int i = 0; i < min(MAX, N); i++) {
		if (!e_num[i].first)break;
		converter[e_num[i].second] = i;
		Q.push(0);
		while (!Q.empty()) {
			cn = Q.front();
			Q.pop();
			for (auto j : edge[cn]) {
				if (lca.depth[cn] > lca.depth[j.to])continue;
				if (j.color != e_num[i].second) {
					dis[i][j.to] = dis[i][cn];
					num[i][j.to] = num[i][cn];
					Q.push(j.to);
				}
				else {
					dis[i][j.to] = dis[i][cn] + j.cost;
					num[i][j.to] = num[i][cn] + 1;
					Q.push(j.to);
				}
			}
		}
	}
	Q.push(0);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (lca.depth[cn] > lca.depth[i.to])continue;
			all_dis[i.to] = all_dis[cn] + i.cost;
			Q.push(i.to);
		}
	}
	for (auto p : q) {
		H = p.color;
		W = p.cost;
		L = p.l;
		R = p.r;
		H--;
		L--;
		R--;
		if (converter[H] == -1) {
			int c = lca.LCA(L, R);
			int ans = all_dis[L] + all_dis[R];
			ans -= all_dis[c] * 2;
			//for (auto i : cedge[H]) {
			//	if (lca.LCA(i.to, L) == i.to && (lca.LCA(i.to, c)) == c)ans += W - i.cost;
			//	else if (lca.LCA(i.to, R) == i.to && (lca.LCA(i.to, c)) == c)ans += W - i.cost;
			//}
			cout << ans << endl;
		}
		else {
			int c = lca.LCA(L, R);
			int ans = all_dis[L] + all_dis[R];
			ans -= all_dis[c] * 2;
			int index = converter[H];
			int add = num[index][L] + num[index][R] - num[index][c] * 2;
			add *= W;
			ans += add;
			ans -= dis[index][L] + dis[index][R] - dis[index][c] * 2;
			cout << ans << endl;
		}
	}
}


Compiler output:
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Iterator2 = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = std::greater<int>]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = greater<int>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:177:6:   required from here
  177 |         sort(e_num.begin(), e_num.end(),greater<int>());
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:30: error: no match for call to '(std::greater<int>) (std::pair<int, int>&, std::pair<int, int>&)'
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:49:
/usr/include/c++/14/bits/stl_function.h:394:7: note: candidate: 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = int]'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:29: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const int&'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = std::pair<int, int>; _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Compare = std::greater<int>]':
/usr/include/c++/14/bits/stl_algo.h:1757:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<greater<int> >]'
 1757 |       while (__comp(__val, __next))
      |              ~~~~~~^~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1785:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1785 |             std::__unguarded_linear_insert(__i,
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
 1786 |                                 __gnu_cxx::__ops::__val_comp_iter(__comp));
      |                                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = greater<int>]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:177:6:   required from here
  177 |         sort(e_num.begin(), e_num.end(),greater<int>());
      |         ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:240:30: error: no match for call to '(std::greater<int>) (std::pair<int, int>&, std::pair<int, int>&)'
  240 |         { return bool(_M_comp(__val, *__it)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:7: note: candidate: 'constexpr bool std::greater<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = int]'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |       ^~~~~~~~
/usr/include/c++/14/bits/stl_function.h:394:29: note:   no known conversion for argument 1 from 'std::pair<int, int>' to 'const int&'
  394 |       operator()(const _Tp& __x, const _Tp& __y) const
      |                  ~~~~~~~~~~~^~~
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >; _Value = std::pair<int, int>; _Compare = std::greater<int>]':
/usr/include/c++/14/bits/stl_heap.h:140:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Distance = long int; _Tp = pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_val<greater<int> >]'
  140 |       while (__holeIndex > __topIndex && __comp(__first + __parent, __value))
      |                                          ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:247:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Distance = long int; _Tp = pair<int, int>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
  247 |       std::__push_heap(__first, __holeIndex, __topIndex,
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  248 |                        _GLIBCXX_MOVE(__value), __cmp);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_heap.h:356:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
  356 |           std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
      |           ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  357 |                              __comp);
      |                              ~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<greater<int> >]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<pair<int, int>*, vector<pair<int, int> > >; _Size = long int; _Compare = __gnu_cx