結果

問題 No.898 tri-βutree
ユーザー MarcusAureliusAntoninusMarcusAureliusAntoninus
提出日時 2019-10-04 22:02:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 196 ms / 4,000 ms
コード長 3,172 bytes
コンパイル時間 2,444 ms
コンパイル使用メモリ 215,128 KB
最終ジャッジ日時 2025-01-07 20:32:13
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:95:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   95 |                 scanf("%d%d%lld", &u, &v, &w);
      |                            ~~~^           ~~
      |                               |           |
      |                               |           int64_t* {aka long int*}
      |                               long long int*
      |                            %ld
main.cpp:120:28: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
  120 |                 printf("%lld\n", ans);
      |                         ~~~^     ~~~
      |                            |     |
      |                            |     int64_t {aka long int}
      |                            long long int
      |                         %ld
main.cpp:89:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   89 |         scanf("%d", &N);
      |         ~~~~~^~~~~~~~~~
main.cpp:95:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   95 |                 scanf("%d%d%lld", &u, &v, &w);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:105:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  105 |         scanf("%d", &Q);
      |         ~~~~~^~~~~~~~~~
main.cpp:109:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  109 |                 scanf("%d%d%d", &x, &y, &z);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~

ソースコード

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