結果

問題 No.898 tri-βutree
コンテスト
ユーザー ldsyb
提出日時 2019-10-05 17:43:00
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,763 bytes
コンパイル時間 2,020 ms
コンパイル使用メモリ 182,832 KB
実行使用メモリ 36,864 KB
最終ジャッジ日時 2024-10-06 12:24:06
合計ジャッジ時間 11,538 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int main()
{
	int64_t n;
	cin >> n;
	vector<vector<pair<int64_t, int64_t>>> g(n);
	for (int64_t i = 0; i < n - 1; i++)
	{
		int64_t a, b, c;
		cin >> a >> b >> c;
		g[a].push_back({b, c});
		g[b].push_back({a, c});
	}

	vector<int64_t> depth(n), d(n);
	vector<vector<int64_t>> pre(30, vector<int64_t>(n));

	{
		stack<int64_t> st;
		vector<bool> done(n, false);

		depth[0] = 0;
		d[0] = 0;
		done[0] = true;
		pre[0][0] = 0;
		st.emplace(0);

		while (!st.empty())
		{
			int64_t v = st.top();
			st.pop();

			for (auto &&p : g[v])
			{
				if (done[p.first])
				{
					continue;
				}
				depth[p.first] = depth[v] + 1;
				d[p.first] = d[v] + p.second;
				done[p.first] = true;
				pre[0][p.first] = v;
				st.emplace(p.first);
			}
		}

		for (int64_t i = 1; i < 30; i++)
		{
			for (int64_t j = 0; j < n; j++)
			{
				pre[i][j] = pre[i - 1][pre[i - 1][j]];
			}
		}
	}

	auto lca = [&](int64_t x, int64_t y) {
		for (int64_t diff = max(int64_t(0), depth[y] - depth[x]), tmp = 0; diff; diff >>= 1, tmp++)
		{
			if (diff & 1)
			{
				y = pre[tmp][y];
			}
		}
		for (int64_t diff = max(int64_t(0), depth[x] - depth[y]), tmp = 0; diff; diff >>= 1, tmp++)
		{
			if (diff & 1)
			{
				x = pre[tmp][x];
			}
		}

		if (x == y)
		{
			return x;
		}
		else
		{
			int64_t ok = 29, ng = -1;
			while (1 < abs(ok - ng))
			{
				int64_t mid = (ok + ng) / 2;
				((pre[mid][x] == pre[mid][y]) ? ok : ng) = mid;
			}
			return pre[ok][x];
		}
	};

	auto dist = [&](int64_t x, int64_t y) {
		return d[x] + d[y] - 2 * d[lca(x, y)];
	};

	int64_t q;
	cin >> q;

	for (int64_t _ = 0; _ < q; _++)
	{
		int64_t x, y, z;
		cin >> x >> y >> z;

		cout << (dist(x, y) + dist(x, z) + dist(y, z)) / 2 << endl;
	}

	return 0;
}
0