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;

//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 bool isPower2(ull a)
{
	if (a == 0)
	{
		return false;
	}
	return !(a & (a - 1));
}

inline ll getMaxEffectiveBit(ull a)
{
	ll index = -1;
	for (; a != 0; a >>= 1)
	{
		++index;
	}
return index;
}

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

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

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

	return result;
}

ll getLCA(ll node1, ll node2, const vector<vector<ll>>& parentNodes, const vector<ll>& depths) {
	if (depths[node1] > depths[node2])
	{
		auto diff = depths[node1] - depths[node2];
		while (diff > 0)
		{
			node1 = parentNodes[node1][getMaxEffectiveBit(diff & -diff)];
			diff -= diff & -diff;
		}
	}
	else if (depths[node1] < depths[node2])
	{
		auto diff = depths[node2] - depths[node1];
		while (diff > 0)
		{
			node2 = parentNodes[node2][getMaxEffectiveBit(diff & -diff)];
			diff -= diff & -diff;
		}
	}

	if (node1 == node2)
	{
		return node1;
	}

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

	return parentNodes[node1][0];
}

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

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

	vector<vector<tuple<ll, ll, ll>>> edges(N);
	ll a, b, c, d;
	for (ll i = 0; i < N - 1; ++i)
	{
		scanf_s("%lld %lld %lld %lld", &a, &b, &c, &d);
		edges[a - 1].emplace_back(b - 1, c, d);
		edges[b - 1].emplace_back(a - 1, c, d);
	}

	vector<ll> depths(N);
	vector<ll> dists(N);

	ll logN = getMaxEffectiveBit(N) + 1;
	vector<vector<ll>> parentNodes(N, vector<ll>(logN + 1));

	map<ll, ll> nodeToPassCount;
	map<ll, map<ll, ll>> colorToNodeCount;
	map<ll, map<ll, ll>> colorToNodeDist;

	map<ll, tuple<ll, ll, ll>> backwardEdges;
	ll passCount = 0;
	vector<ll> colorCount(N);
	vector<ll> colorDist(N);

	vector<bool> haveChecked(N, false);
	stack<ll> searchNodes;

	searchNodes.emplace(0LL);
	for (ll i = 0; i <= logN; ++i)
	{
		parentNodes[0LL][i] = 0LL;
	}
	nodeToPassCount[0LL] = passCount++;
	depths[0LL] = 0LL;
	dists[0LL] = 0LL;
	haveChecked[0LL] = true;

	while (!searchNodes.empty())
	{
		ll startNode = searchNodes.top();
		searchNodes.pop();

		if (backwardEdges.count(startNode) > 0)
		{
			auto edge = backwardEdges[startNode];
			auto node = get<0>(edge);
			auto color = get<1>(edge);
			auto length = get<2>(edge);

			depths[startNode] = depths[node] + 1;
			dists[startNode] = dists[node] + length;

			++colorCount[color];
			colorDist[color] += length;

			colorToNodeCount[color][passCount] = colorCount[color];
			colorToNodeDist[color][passCount] = colorDist[color];

			nodeToPassCount[startNode] = passCount++;
		}

		for (auto edge : edges[startNode])
		{
			auto endNode = get<0>(edge);
			auto color = get<1>(edge);
			auto length = get<2>(edge);
			if (haveChecked[endNode])
			{
				continue;
			}

			parentNodes[endNode][0] = startNode;
			for (ll i = 0; i < logN; ++i)
			{
				parentNodes[endNode][i + 1] = parentNodes[parentNodes[endNode][i]][i];
			}

			backwardEdges[endNode] = tuple<ll, ll, ll>( startNode, color, length );

			searchNodes.push(endNode);
			haveChecked[endNode] = true;
		}

		if (!searchNodes.empty() && edges[startNode].size() == 1)
		{
			do {
				auto edge = backwardEdges[startNode];
				startNode = get<0>(edge);
				auto color = get<1>(edge);
				auto length = get<2>(edge);
				
				--colorCount[color];
				colorDist[color] -= length;

				colorToNodeCount[color][passCount] = colorCount[color];
				colorToNodeDist[color][passCount] = colorDist[color];

				++passCount;
			} while (startNode != parentNodes[searchNodes.top()][0]);
		}
	}
	
	cout << "aaa" << endl;

	ll x, y, u, v;
	for (ll i = 0; i < Q; ++i)
	{
		scanf_s("%lld %lld %lld %lld", &x, &y, &u, &v);
		--u, --v;

		auto w = getLCA(u, v, parentNodes, depths);
		
		auto dist = dists[u] + dists[v] - dists[w] * 2;

		if (colorToNodeCount.count(x) > 0)
		{
			auto nodeCount = colorToNodeCount[x];

			auto passCount = nodeToPassCount[u];
			auto iter = nodeCount.upper_bound(passCount);
			if (iter != nodeCount.begin())
			{
				dist += (--iter)->second * y;
			}

			passCount = nodeToPassCount[v];
			iter = nodeCount.upper_bound(passCount);
			if (iter != nodeCount.begin())
			{
				dist += (--iter)->second * y;
			}

			passCount = nodeToPassCount[w];
			iter = nodeCount.upper_bound(passCount);
			if (iter != nodeCount.begin())
			{
				dist -= (--iter)->second * 2 * y;
			}
		}

		if (colorToNodeDist.count(x) > 0)
		{
			auto nodeDist = colorToNodeDist[x];

			auto passCount = nodeToPassCount[u];
			auto iter = nodeDist.upper_bound(passCount);
			if (iter != nodeDist.begin())
			{
				dist -= (--iter)->second;
			}

			passCount = nodeToPassCount[v];
			iter = nodeDist.upper_bound(passCount);
			if (iter != nodeDist.begin())
			{
				dist -= (--iter)->second;
			}
			passCount = nodeToPassCount[w];
			iter = nodeDist.upper_bound(passCount);
			if (iter != nodeDist.begin())
			{
				dist += (--iter)->second * 2;
			}
		}

		printf("%d\n", dist);
	}


	cout << "bbb" << endl;


	return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:171:17: error: 'scanf_s' was not declared in this scope; did you mean 'scanf'?
  171 |                 scanf_s("%lld %lld %lld %lld", &a, &b, &c, &d);
      |                 ^~~~~~~
      |                 scanf
a.cc:274:17: error: 'scanf_s' was not declared in this scope; did you mean 'scanf'?
  274 |                 scanf_s("%lld %lld %lld %lld", &x, &y, &u, &v);
      |                 ^~~~~~~
      |                 scanf