結果

問題 No.898 tri-βutree
ユーザー yakkiyakki
提出日時 2019-10-09 04:08:32
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 439 ms / 4,000 ms
コード長 2,616 bytes
コンパイル時間 1,024 ms
コンパイル使用メモリ 109,424 KB
実行使用メモリ 19,544 KB
最終ジャッジ日時 2024-11-08 23:02:24
合計ジャッジ時間 9,743 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 288 ms
19,544 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 1 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 426 ms
17,328 KB
testcase_08 AC 431 ms
17,340 KB
testcase_09 AC 437 ms
17,328 KB
testcase_10 AC 425 ms
17,328 KB
testcase_11 AC 405 ms
17,332 KB
testcase_12 AC 418 ms
17,324 KB
testcase_13 AC 417 ms
17,332 KB
testcase_14 AC 426 ms
17,328 KB
testcase_15 AC 426 ms
17,332 KB
testcase_16 AC 425 ms
17,328 KB
testcase_17 AC 425 ms
17,280 KB
testcase_18 AC 435 ms
17,456 KB
testcase_19 AC 434 ms
17,328 KB
testcase_20 AC 439 ms
17,332 KB
testcase_21 AC 424 ms
17,328 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

vector<vector<Pi>> G;

void dijkstra(int p,vector<ll> &dist,vector<bool> visited){
	priority_queue<pair<ll,int>> q;
	dist[p] = 0;
	q.push(make_pair(0,p));
	while(!q.empty()){
		pair<ll,int> f = q.top();
		q.pop();
		int u = f.second;

		if(dist[u] < f.first*(-1)) continue;
		visited[u] = true;

		rep(i,G[u].size()){
			int v = G[u][i].first;
			if(visited[v] == true) continue;

			if(dist[v] > dist[u] + G[u][i].second){
				dist[v] = dist[u] + G[u][i].second;
				q.push(make_pair(dist[v]*(-1),v));
			}
		}


	}

}

template<typename T>
class LCA{
	public:
		const int n = 0;
		const int log2_n = 0;
		vector<vector<int>> par;
		vector<int> depth;

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

		void dfs(const T &g,int v,int p,int d){
			par[0][v] = p;
			depth[v] = d;
			for(auto &e : g[v]){
				if(e.first != p) dfs(g,e.first,v,d+1);
			}
		}

		int get(int u,int v){
			if(depth[u] > depth[v]) swap(u,v);
			rep(k,log2_n){
				if((depth[v]-depth[u]) >> k&1){
					v = par[k][v];
				}
			}
			if(u == v) return u;
			for(int k = log2_n-1; k >= 0; k--){
				if(par[k][u] != par[k][v]){
					u = par[k][u];
					v = par[k][v];
				}
			}
			return par[0][u];
		}
};

int main(){
    int N; cin >> N;
    G.resize(N);
    rep(i,N-1){
        int u,v,w; cin >> u >> v >> w;
        G[u].emplace_back(v,w);
        G[v].emplace_back(u,w);
    }
    vector<ll> dist(N,LINF);
    vector<bool> visited(N,false);
    dijkstra(0,dist,visited);
    LCA<vector<vector<Pi>>> l(G,0);
    int Q; cin >> Q;
    while(Q--){
        int x,y,z; cin >> x >> y >> z;
        int d1 = l.get(x,y);
        int d2 = l.get(y,z);
        int d3 = l.get(z,x);
        ll ans = 0;
        ans += dist[x]+dist[y]-dist[d1]*2;
        ans += dist[y]+dist[z]-dist[d2]*2;
        ans += dist[z]+dist[x]-dist[d3]*2;
        ans /= 2;
        cout << ans << endl;

    }

}
0