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 = 1250;

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;
	}
};

int depth[100000];
int parent[100005][17];

class Lowest_Common_Ancestor {
	vector<vector<int>>edge;
	int height = 0;
	int node;
public:
	Lowest_Common_Ancestor(int num) {
		num++;
		node = num;
		while (num) {
			height++;
			num /= 2;
		}
		edge.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[rtnode][0] = -1;
		for (int i = 1; i < node; i++) {
			for (auto j : edge[i]) {
				if (depth[i] - 1 == depth[j]) {
					parent[i][0] = j;
					break;
				}
			}
		}
		for (int i = 0; i < height - 1; i++) {
			for (int j = 0; j < node; j++) {
				if (parent[j][i] < 0)parent[j][i + 1] = -1;
				else parent[j][i + 1] = parent[parent[j][i]][i];
			}
		}
		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[v][i];
				if (depth[v] == depth[u])break;
			}
		}
		if (u == v)return u;
		for (int i = height - 1; i >= 0; i--) {
			if (parent[v][i] != parent[u][i]) {
				u = parent[u][i];
				v = parent[v][i];
			}
		}
		return parent[u][0];
	}
	int Dist(int u, int v) {
		return depth[u] + depth[v] - depth[LCA(u, v)] * 2;
	}
};

struct CEdge {
	int from, to, cost;
	CEdge(int a, int b, int d) {
		from = a, to = b, 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[100000][MAX];
int dis[100000][MAX];
int converter[100000];
int all_dis[100000];
int qnum[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);
		edge[L].push_back(Edge(R, H, W));
		edge[R].push_back(Edge(L, H, W));
	}
	vector<Query>q;
	for (int i = 0; i < K; i++) {
		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 (depth[i] < depth[j.to]) {
				e_num[j.color].first++;
				cedge[j.color].push_back(CEdge(i, j.to, j.cost));
			}
		}
	}
	for (int i = 0; i < N; i++) {
		e_num[i].second = i;
		e_num[i].first *= qnum[i];
	}
	sort(e_num.begin(), e_num.end());
	reverse(e_num.begin(), e_num.end());
	int prec = 0;
	for (int i = 0; i < N; i++) {
		converter[e_num[i].second] = i;
		if (i >= min(MAX, N) || !e_num[i].first)converter[e_num[i].second] -= 10000000;
		else prec = i;
	}
	//for (int i = 0; i < min(MAX, N); i++) {
	//	converter[e_num[i].second] = i;
	//}
	queue<int>Q;
	Q.push(0);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto j : edge[cn]) {
			if (depth[cn] > depth[j.to])continue;
			Q.push(j.to);
			for (int i = 0; i <=prec; i++) {
			//for (int i = 0; i < min(MAX, N); i++) {
				dis[j.to][i] = dis[cn][i];
				num[j.to][i] = num[cn][i];
			}
			if (converter[j.color] >= 0) {
				dis[j.to][converter[j.color]] += j.cost;
				num[j.to][converter[j.color]] ++;
			}
		}
	}
	Q.push(0);
	while (!Q.empty()) {
		int cn = Q.front();
		Q.pop();
		for (auto i : edge[cn]) {
			if (depth[cn] > depth[i.to])continue;
			all_dis[i.to] = all_dis[cn] + i.cost;
			Q.push(i.to);
		}
	}
	for (int i = 0; i < K; i++) {
		H = q[i].color;
		W = q[i].cost;
		L = q[i].l;
		R = q[i].r;
		H--;
		L--;
		R--;
		int cnt = 0;
		if (converter[H] < 0) {
			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 (cnt >= 2000000)return;
				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;
				cnt++;

			}
			cout << ans << "\n";
		}
		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[L][index] + num[R][index] - num[c][index] * 2;
			add *= W;
			ans += add;
			ans -= dis[L][index] + dis[R][index] - dis[c][index] * 2;
			cout << ans << "\n";
		}
	}
}


Compiler output:
a.cc: In function 'int main()':
a.cc:226:52: error: return-statement with no value, in function returning 'int' [-fpermissive]
  226 |                                 if (cnt >= 2000000)return;
      |                                                    ^~~~~~