Tietoverkko

#include <math.h>
#include <iostream>
#include <map>
#include <vector>
#define L long long
using namespace std;

void definef();
vector<L> erittely(L k);
pair<L,L> ylos(L a, L k);
pair<L, L> ylos(L a, L k, L c);
L f(L x, L k);
L etsi(L a, L b);


map<L, pair<pair<L, L>, L>> m = { {1, { {0, 0}, 1 }} };
map<L, map<L, pair<L, L>>> fx;

L n;

int main()
{
	L a, b, x, k = 0;
	cin >> n;

	L kerros = 1;
	L e = 0;
	for (L i = 0; i < n - 1; i++)
	{
		cin >> a >> b >> x;
		if (a < e) kerros = m[a].second;
		e = b;
		kerros++;

		m[b] = { {a, x}, kerros };
	}

	definef();

	for (L i = 1; i < n; i++)
	{
		for (L j = i + 1; j < n + 1; j++)
		{
			k += etsi(i, j);
		}
	}
	cout << k << "\n";
}

void definef()
{
	for (L i = 1; i <= n; i *= 2)
	{
		for (L j = 1 + i; j <= n; j++)
		{
			pair<L,L> p = ylos(j, i);
			fx[i][j] = p;
		}
	}
}

vector<L> erittely(L k)
{
	vector<L> komponentit;
	L sum = 0;
	L i = 0;
	L kom = 0;
	while (true)
	{
		kom = powl(2, i);
		if (kom > k)
		{
			kom = powl(2, i - 1);
			komponentit.push_back(kom);
			sum = kom;
			break;
		}
		else if (kom == k)
		{
			komponentit.push_back(kom);
			sum = kom;
			break;
		}
		i++;
	}
	while (sum != k)
	{
		kom = kom / 2;
		if (kom + sum <= k)
		{
			kom *= 2;
			komponentit.push_back(kom);
			sum += kom;
		}
	}
	return komponentit;
}

pair<L,L> ylos(L a, L k)
{
	L minx = 1000000000;
	for (L i = 0; i < k; i++)
	{
		if (a == 1) break;
		if (minx == 1) break;
		if (m[a].first.second < minx) minx = m[a].first.second;
		a = m[a].first.first;
	}

	if (minx == 1000000000)
	{
		pair<L, L> p = { a, 0 };
		return p;
	}
	pair<L, L> p = { a, minx };
	return p;
}

pair<L, L> ylos(L a, L k, L c)
{
	L minx = 1000000000;
	for (L i = 0; i < k; i++)
	{
		if (a == 1) break;
		if (minx == 1) break;
		if (m[a].first.second < minx) minx = m[a].first.second;
		a = m[a].first.first;
	}
	if (c < minx) minx = c;

	if (minx == 1000000000)
	{
		pair<L, L> p = { a, 0 };
		return p;
	}
	pair<L, L> p = { a, minx };
	return p;
}

L f(L x, L k)
{
	vector<L> komponentit = erittely(k);
	L c = 0;
	for (auto kom : komponentit)
	{
		c = fx[kom][x].second;
		if (fx[kom][x].first == 1 || c == 1) break;
		x = fx[kom][x].first;
	}
	return c;
}

L etsi(L a, L b)
{
	L c = 1000000000, c2 = 1000000000, d = m[a].second - m[b].second;
	if (d < 0) c2 = f(b, -d);
	else if (d > 0) c = f(a, d);

	if (a == b)
	{
		c = m[a].first.second;
	}
	else
	{
		pair<L, L> p;
		while (a != b)
		{
			if (a != 1) 
			{
				p = ylos(a, 1, c);
				a = p.first;
				c = p.second;
			}

			if (b != 1) 
			{ 
				p = ylos(b, 1, c2);
				b = p.first;
				c2 = p.second;
			}
		}
	}
	if (c == 0 && c2 != 0) return c2;
	else if (c != 0 && c2 == 0) return c;
	else if (c < c2) return c;
	else if (c > c2) return c2;
	return c;
}

Test 1

Group: 1, 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED