結果

問題 No.898 tri-βutree
ユーザー momoharamomohara
提出日時 2020-02-16 13:16:05
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 219 ms / 4,000 ms
コード長 3,374 bytes
コンパイル時間 1,571 ms
コンパイル使用メモリ 109,496 KB
実行使用メモリ 27,488 KB
最終ジャッジ日時 2023-08-08 16:38:14
合計ジャッジ時間 7,350 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
27,488 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 210 ms
20,032 KB
testcase_08 AC 210 ms
19,984 KB
testcase_09 AC 211 ms
19,924 KB
testcase_10 AC 218 ms
19,972 KB
testcase_11 AC 219 ms
19,976 KB
testcase_12 AC 218 ms
19,972 KB
testcase_13 AC 216 ms
19,920 KB
testcase_14 AC 217 ms
20,032 KB
testcase_15 AC 219 ms
19,984 KB
testcase_16 AC 215 ms
20,024 KB
testcase_17 AC 217 ms
19,808 KB
testcase_18 AC 217 ms
19,972 KB
testcase_19 AC 216 ms
19,988 KB
testcase_20 AC 217 ms
19,904 KB
testcase_21 AC 219 ms
19,900 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;
const int loose = 0;
const int tight = 1;

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

class lca {
public:
	const int n = 0;
	const int log2_n = 0;
	vector<vector<int>> parent;
	vector<int> depth;

	lca() {}

	lca(const Graph& g, int root)
		: n(g.size()), log2_n(log2(n) + 1), parent(log2_n, vector<int>(n)), depth(n) {
		dfs(g, root, -1, 0);
		for (int k = 0; k + 1 < log2_n; k++) {
			for (int v = 0; v < (int)g.size(); v++) {
				if (parent[k][v] < 0)
					parent[k + 1][v] = -1;
				else
					parent[k + 1][v] = parent[k][parent[k][v]];
			}
		}
	}

	//深さを求める＋1個上の親を保存
	void dfs(const Graph& g, int v, int p, int d) {
		parent[0][v] = p;
		depth[v] = d;
		for (auto& e : g[v]) {
			if (e.to != p) dfs(g, e.to, v, d + 1);
		}
	}

	//LCA(最小共通祖先)をえる
	int get(int u, int v) {
		//頂点の深さをあわせるために、深さが浅い法を遡らせる
		if (depth[u] > depth[v]) std::swap(u, v);
		for (int k = 0; k < log2_n; k++) {
			if ((depth[v] - depth[u]) >> k & 1) {
				v = parent[k][v];
			}
		}

		//降順で親が一致しない場合は遡る
		if (u == v) return u;
		for (int k = log2_n - 1; k >= 0; k--) {
			if (parent[k][u] != parent[k][v]) {
				u = parent[k][u];
				v = parent[k][v];
			}
		}
		return parent[0][u];
	}

	//最短経路
	int d(int u, int v) {
		return depth[u] + depth[v] - 2 * depth[get(u, v)];
	}
};

void dfs(const Graph& g, Array& depth, int v, int p, ll d) {
	depth[v] = d;
	for (auto& e : g[v]) {
		if (e.to != p) dfs(g, depth, e.to, v, d + e.cap);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	ll n;
	cin >> n;
	Graph g(n);

	REP(i, n-1) {
		ll x,y,c;
		cin >> x>>y>>c;
		add_edge(g, x, y, c, true, c);
	}

	lca lc(g, 0);
	Array d(n);
	dfs(g, d, 0, -1, 0);

	ll q;
	cin >> q;
	while (q--) {
		ll ans = INF;
		int v[3];
		REP(i, 3)cin >> v[i];
		REP(i, 3) {
			int m = lc.get(v[i], v[(i+1)%3]);
			ll dd = d[v[i]] + d[v[(i+1)%3]] - 2 * d[m];
			dd += d[v[(i+2)%3]] + d[m] - 2 * d[lc.get(v[(i+2)%3], m)];
			chmin(ans, dd);
		}
		cout << ans << en;
	}

	return 0;
}
0