結果

問題 No.898 tri-βutree
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-10-04 22:02:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 206 ms / 4,000 ms
コード長 3,172 bytes
コンパイル時間 2,999 ms
コンパイル使用メモリ 224,108 KB
実行使用メモリ 26,368 KB
最終ジャッジ日時 2024-11-08 22:12:06
合計ジャッジ時間 7,523 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 96 ms
26,368 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 192 ms
22,144 KB
testcase_08 AC 190 ms
22,144 KB
testcase_09 AC 194 ms
22,144 KB
testcase_10 AC 193 ms
22,144 KB
testcase_11 AC 192 ms
22,144 KB
testcase_12 AC 195 ms
22,144 KB
testcase_13 AC 206 ms
22,144 KB
testcase_14 AC 201 ms
22,272 KB
testcase_15 AC 198 ms
22,144 KB
testcase_16 AC 187 ms
22,144 KB
testcase_17 AC 194 ms
22,144 KB
testcase_18 AC 201 ms
22,144 KB
testcase_19 AC 199 ms
22,272 KB
testcase_20 AC 204 ms
22,144 KB
testcase_21 AC 206 ms
22,144 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