Language: C++

#include <bits/stdc++.h>
using namespace std;

const int N = (int) 2e5 + 5;
const int LOGN = (int) log2(N) + 3;
const int INF = (int) 1e9 + 9;

struct TData {
	int c, w;
	TData() {}
	TData(int c, int w) : c(c), w(w) {}
	bool operator < (const TData &op) const {
		return c == op.c ? w < op.w : c < op.c;
	}
};

struct TEdge {
	int v, c, w;
	TEdge() {}
	TEdge(int v, int c, int w) : v(v), c(c), w(w) {}
};

struct TNode {
	int in, ou, c, w;
	TNode() {}
	TNode(int in, int ou, int c, int w) : in(in), ou(ou), c(c), w(w) {}
	bool operator < (const TNode &op) const {
		return in == op.in ? ou < op.ou : in < op.in;
	}
	void out() {
		cout << in << " " << ou << " " << c << " " << w << endl;
	}
} node[N];

struct TQuery {
	int c, w, u, v, idx;
	int res[3];
	TQuery() {
		c = w = u = v = idx = 0;
		for (int x = 0; x < 3; x++) res[x] = 0;
	}
	TQuery(int c, int w, int u, int v, int idx) : c(c), w(w), u(u), v(v), idx(idx) {}
} query[N];

int n, q;
vector <TData> st[N << 2];
vector <TEdge> g[N];
vector <long long> sum[N << 2];

int vtime;
int in[N], ou[N], nodeOfou[N];
TEdge edgeNode[N];

int logn;
int depth[N];
int dad[N][LOGN];
long long dist[N];
int ans[N];

int pos;
int cntQuery[N][3];
long long sumQuery[N][3];

void dfsEulerTour(int u, int p) {
	in[u] = ++vtime;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].v;
		int w = g[u][i].w;
		if (v == dad[u][0]) continue;
		edgeNode[v] = g[u][i];
		depth[v] = depth[u] + 1;
		dist[v] = dist[u] + w;
		dfsEulerTour(v, dad[v][0] = u);
	}
	ou[u] = ++vtime;
}

void buildLca() {
	for (int k = 1; k <= logn; k++)
		for (int i = 1; i <= n; i++) dad[i][k] = dad[dad[i][k - 1]][k - 1];
}

int findLca(int u, int v) {
	for (int k = logn; k >= 0; k--)
		if (depth[dad[u][k]] >= depth[v]) u = dad[u][k];
	for (int k = logn; k >= 0; k--)
		if (depth[dad[v][k]] >= depth[u]) v = dad[v][k];
	if (u == v) return u;
	for (int k = logn; k >= 0; k--)
		if (dad[u][k] != dad[v][k]) {
			u = dad[u][k];
			v = dad[v][k];
		}
	return dad[u][0];
}

void combine(int k) {
	vector <TData> left = st[k << 1], right = st[k << 1 | 1];
	vector <TData> ans; ans.clear(); ans.push_back(TData(0, 0));
	vector <long long> s; s.clear(); s.push_back(0);
	int i = 1, j = 1;
	while (i < left.size() && j < right.size())
		if (left[i].c == right[j].c) {
			left[i].w < right[j].w ? ans.push_back(left[i++]) : ans.push_back(right[j++]); 
		} else {
			left[i].c < right[j].c ? ans.push_back(left[i++]) : ans.push_back(right[j++]); 
		}
	while (i < left.size()) ans.push_back(left[i++]);
	while (j < right.size()) ans.push_back(right[j++]);
	long long tmp = 0;
	for (int i = 1; i < ans.size(); i++) {
		tmp += ans[i].w;
		s.push_back(tmp);
	}
	st[k] = ans; sum[k] = s;
}

void update(int k, int l, int r, int i, int c, long long w) {
	if (i < l || i > r) return;
	if (l == r) {
		st[k].push_back(TData(0, 0)); sum[k].push_back(0);
		st[k].push_back(TData(c, w)); sum[k].push_back(w);
		return;
	}	
	int m = (l + r) >> 1;
	update(k << 1, l, m, i, c, w);
	update(k << 1 | 1, m + 1, r, i, c, w);
	combine(k);
}

pair <int, long long> get(int k, int l, int r, int i, int j, int color) {
	if (i > j) return makr_pair(0, 0LL);
	if (j < l || i > r) return make_pair(0, 0LL);
	if (i <= l && j >= r) {
		int right = upper_bound(st[k].begin(), st[k].end(), TData(color, INF)) - st[k].begin() - 1;
		int left  = lower_bound(st[k].begin(), st[k].end(), TData(color, -INF)) - st[k].begin();
		if (right >= left && left >= 1 && right < st[k].size()) {
			int cnt = right - left + 1;
			long long sumEdge = sum[k][right] - sum[k][left - 1];
			// cerr << "#: " << cnt << " " << sumEdge << endl;
			return make_pair(cnt, sumEdge);
		} else return make_pair(0, 0LL);
	}
	int m = (l + r) >> 1;
	pair <int, long long> left = get(k << 1, l, m, i, j, color);
	pair <int, long long> right = get(k << 1 | 1, m + 1, r, i, j, color);
	pair <int, long long> ans = make_pair(left.first + right.first, left.second + right.second);
	return ans;
}

void init() {
	logn = log2(n) + 1;
	dad[1][0] = 0;
	depth[1] = 1;
	dfsEulerTour(1, 0);
	buildLca();
	for (int i = 1; i <= n; i++) node[i] = TNode(in[i], ou[i], edgeNode[i].c, edgeNode[i].w);
	sort(node + 1, node + 1 + n);
	// for (int i = 1; i <= n; i++) node[i].ou(); cou << endl;
	for (int i = 1; i <= n; i++) nodeOfou[ou[i]] = i;
}

bool compFoo(TQuery o1, TQuery o2) {
	return in[o1.u] < in[o2.u];
}

bool compBar(TQuery o1, TQuery o2) {
	return in[o1.v] < in[o2.v];
}

bool compLca(TQuery o1, TQuery o2) {
	int lca1 = findLca(o1.u, o1.v);
	int lca2 = findLca(o2.u, o2.v);
	return in[lca1] < in[lca2];
}

void processFoo() {
	sort(query + 1, query + 1 + q, compFoo);
	pos = 1;
	for (int i = 1; i <= q; i++) {
		int idx = query[i].idx;
		int u = query[i].u, c = query[i].c;
		while (pos <= n && node[pos].in <= in[u]) {
			update(1, 1, n << 1, node[pos].ou, node[pos].c, node[pos].w);
			pos++;
		}
		pair <int, long long> resRight = get(1, 1, 2 * n, 1, 2 * n, c);
		pair <int, long long> resLeft  = get(1, 1, 2 * n, 1, ou[u], c);
		cntQuery[idx][0] = resRight.first - resLeft.first;
		sumQuery[idx][0] = resRight.second - resLeft.second; 
	}
/*	for (int i = 1; i <= q; i++) {
		cout << "#u: " << cntQuery[i][0] << " " << sumQuery[i][0] << endl;
	}*/
	for (int i = 0; i < (N << 2) - 3; i++) {
		sum[i].clear();
		st[i].clear();
	}
}

void processBar() {
	sort(query + 1, query + 1 + q, compBar);
	pos = 1;
	for (int i = 1; i <= q; i++) {
		int idx = query[i].idx;
		int v = query[i].v, c = query[i].c;
		while (pos <= n && node[pos].in <= in[v]) {
			update(1, 1, n << 1, node[pos].ou, node[pos].c, node[pos].w);
			pos++;
		}

		pair <int, long long> resRight = get(1, 1, n << 1, 1, n << 1, c);
		pair <int, long long> resLeft  = get(1, 1, n << 1, 1, ou[v] - 1, c);
		// cout << "~" << pos << " " << v << " " << resLeft.first << " " << resRight.first << endl;
		cntQuery[idx][1] = resRight.first - resLeft.first;
		sumQuery[idx][1] = resRight.second - resLeft.second; 
	}
/*	for (int i = 1; i <= q; i++) {
		cout << "#v: " << cntQuery[i][1] << " " << sumQuery[i][1] << endl;
	}*/
	for (int i = 0; i < (N << 2) - 3; i++) {
		sum[i].clear();
		st[i].clear();
	}
}

void processLca() {
	sort(query + 1, query + 1 + q, compLca);
	pos = 1;
	for (int i = 1; i <= q; i++) {
		int idx = query[i].idx;
		int p = findLca(query[i].u, query[i].v), c = query[i].c;
		while (pos <= n && node[pos].in <= in[p]) {
			update(1, 1, n << 1, node[pos].ou, node[pos].c, node[pos].w);
			pos++;
		}
		pair <int, long long> resRight = get(1, 1, 2 * n, 1, 2 * n, c);
		pair <int, long long> resLeft  = get(1, 1, 2 * n, 1, ou[p], c);
		cntQuery[idx][2] = resRight.first - resLeft.first;
		sumQuery[idx][2] = resRight.second - resLeft.second; 
	}
/*	for (int i = 1; i <= q; i++) {
		cout << "#p: " << cntQuery[i][2] << " " << sumQuery[i][2] << endl;
	}*/
	for (int i = 0; i < (N << 2) - 3; i++) {
		sum[i].clear();
		st[i].clear();
	}
}

int main() {
	// freopen("in.inp", "r", stdin); 
	//freopen(".ou", "w", stdou);
	scanf("%d %d", &n, &q);
	for (int i = 1; i < n; i++) {
		int u, v, c, w; scanf("%d %d %d %d", &u, &v, &c, &w);
		g[u].push_back(TEdge(v, c, w));
		g[v].push_back(TEdge(u, c, w));
	}
	init();
	for (int i = 1; i <= q; i++) {
		int c, w, u, v; scanf("%d %d %d %d", &c, &w, &u, &v);
		query[i] = TQuery(c, w, u, v, i);
	}
	for (int i = 1; i <= n; i++) {
		node[i] = TNode(in[i], ou[i], edgeNode[i].c, edgeNode[i].w);
	}
	sort(node + 1, node + 1 + n);
	processFoo();
	processBar();
	processLca();
	for (int i = 1; i <= q; i++) {
		int u = query[i].u, v = query[i].v, c = query[i].c, w = query[i].w, idx = query[i].idx;
		long long cntRes = cntQuery[idx][0] + cntQuery[idx][1] - 2 * cntQuery[idx][2];
		long long sumRes = sumQuery[idx][0] + sumQuery[idx][1] - 2 * sumQuery[idx][2];
		long long result = dist[u] + dist[v] - 2 * dist[findLca(u, v)];
		result -= sumRes;
		result += 1LL * cntRes * w;
		ans[idx] = result;
	}
	for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
	return 0;
}

/*
5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4
*/

Compiler output:
a.cc: In function 'std::pair<int, long long int> get(int, int, int, int, int, int)':
a.cc:132:27: error: 'makr_pair' was not declared in this scope
  132 |         if (i > j) return makr_pair(0, 0LL);
      |                           ^~~~~~~~~