結果

問題 No.898 tri-βutree
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-10-04 22:02:40
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 217 ms / 4,000 ms
コード長 3,172 bytes
コンパイル時間 4,307 ms
コンパイル使用メモリ 220,364 KB
実行使用メモリ 26,088 KB
最終ジャッジ日時 2023-08-08 15:59:01
合計ジャッジ時間 9,144 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 109 ms
26,088 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 215 ms
21,692 KB
testcase_08 AC 217 ms
21,864 KB
testcase_09 AC 205 ms
21,756 KB
testcase_10 AC 197 ms
22,032 KB
testcase_11 AC 205 ms
21,888 KB
testcase_12 AC 202 ms
21,620 KB
testcase_13 AC 209 ms
21,828 KB
testcase_14 AC 203 ms
21,864 KB
testcase_15 AC 210 ms
21,820 KB
testcase_16 AC 203 ms
22,036 KB
testcase_17 AC 201 ms
21,828 KB
testcase_18 AC 197 ms
21,860 KB
testcase_19 AC 215 ms
21,864 KB
testcase_20 AC 208 ms
21,764 KB
testcase_21 AC 201 ms
22,040 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

struct Edge {
	int to;
	int64_t dist{1};
};
using EdgeVec = std::vector<Edge>;
using EdgeLists = std::vector<EdgeVec>;

///////////////////
// 木の祖先クエリ //
///////////////////

// コンストラクタに渡す木は子に向かう有向グラフでも無向グラフでもいい
// Edgeは{to}
class TreeAncestor {
private:
	using vi = std::vector<int>;
	using vvi = std::vector<vi>;

	const EdgeLists& edges_;
	vvi ancestors_;
	vi depthList_;
	const int root_;

	void initDFS(const int index, const int parent, const int depth)
	{
		ancestors_[index].front() = parent;
		depthList_[index] = depth;
		for (auto& e: edges_[index])
			if (e.to != parent)
				initDFS(e.to, index, depth + 1);
	}
	
public:
	const vi& depthList;

	TreeAncestor(const EdgeLists& adjacentList, const int root)
		: edges_(adjacentList), root_(root), depthList(depthList_)
	{
		int size{1};
		while (1 << (size - 1) <= (int)edges_.size()) size++;
		ancestors_.resize(edges_.size(), vi(size));
		depthList_.resize(edges_.size());
		initDFS(root_, root_, 0);
		for (int i{1}; i < size; i++)
			for (auto& e: ancestors_)
				e[i] = ancestors_[e[i - 1]][i - 1];
	}

	// fromからdistanceだけ根の方向にさかのぼった頂点のindexを返す
	int calcAncestor(const int from, const int distance) const
	{
		int ret{from};
		for (int digit{}, rest{distance}; rest > 0; rest >>= 1, digit++)
			if (rest & 1)
				ret = ancestors_[ret][digit];
		return ret;
	}

	// index0とindex1の最近共通祖先のindexを返す
	int calcLCA(int index0, int index1) const
	{
		if (depthList_[index0] > depthList_[index1])
			index0 = calcAncestor(index0, depthList_[index0] - depthList_[index1]);
		else
			index1 = calcAncestor(index1, depthList_[index1] - depthList_[index0]);
		if (index0 == index1) return index0;
		
		for (int digit{(int)ancestors_.front().size() - 1}; digit >= 0; digit--)
			if (ancestors_[index0][digit] != ancestors_[index1][digit])
			{
				index0 = ancestors_[index0][digit];
				index1 = ancestors_[index1][digit];
			}
		return ancestors_[index0][0];
	}
};

EdgeLists edges;
std::vector<bool> visited;
std::vector<int64_t> depth;

void dfs(int index);

int main()
{
	int N;
	scanf("%d", &N);
	edges.resize(N);
	for (int i{}; i < N - 1; i++)
	{
		int u, v;
		int64_t w;
		scanf("%d%d%lld", &u, &v, &w);
		edges[u].push_back({v, w});
		edges[v].push_back({u, w});
	}
	TreeAncestor tree(edges, 0);
	visited.resize(N);
	depth.resize(N);
	dfs(0);

	int Q;
	scanf("%d", &Q);
	for (int i{}; i < Q; i++)
	{
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		int lca_xy{tree.calcLCA(x, y)}, lca_xyz{tree.calcLCA(lca_xy, z)};
		int64_t ans{depth[x] + depth[y] - 2 * depth[lca_xy]};
		if (lca_xyz == lca_xy)
		{
			int lca_xz{tree.calcLCA(x, z)}, lca_yz{tree.calcLCA(y, z)};
			if (lca_yz == lca_xy) ans += depth[z] - depth[lca_xz];
			else ans += depth[z] - depth[lca_yz];
		}
		else
			ans += depth[z] + depth[lca_xy] - 2 * depth[lca_xyz];
		printf("%lld\n", ans);
	}

	return 0;
}

void dfs(int index)
{
	visited[index] = true;
	for (auto& e: edges[index])
	{
		if (visited[e.to]) continue;
		depth[e.to] = depth[index] + e.dist;
		dfs(e.to);
	}
}
0