結果

問題 No.898 tri-βutree
ユーザー okok
提出日時 2019-10-04 22:10:00
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 521 ms / 4,000 ms
コード長 2,596 bytes
コンパイル時間 1,201 ms
コンパイル使用メモリ 94,528 KB
実行使用メモリ 31,872 KB
最終ジャッジ日時 2023-08-08 16:00:37
合計ジャッジ時間 11,594 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 302 ms
31,872 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 1 ms
4,376 KB
testcase_07 AC 508 ms
26,996 KB
testcase_08 AC 512 ms
27,000 KB
testcase_09 AC 507 ms
27,244 KB
testcase_10 AC 506 ms
26,948 KB
testcase_11 AC 499 ms
27,040 KB
testcase_12 AC 504 ms
27,092 KB
testcase_13 AC 498 ms
27,084 KB
testcase_14 AC 521 ms
27,068 KB
testcase_15 AC 502 ms
27,060 KB
testcase_16 AC 504 ms
27,148 KB
testcase_17 AC 493 ms
27,144 KB
testcase_18 AC 498 ms
27,216 KB
testcase_19 AC 503 ms
27,268 KB
testcase_20 AC 502 ms
27,148 KB
testcase_21 AC 499 ms
27,004 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

#define int long long
#define endl "\n"

const long long INF = (long long)1e18;
const long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}

struct edge{
	int to, cost;
};


vector<vector<edge>> G;


vector<int> depth;
vector<vector<int>> table;

void dfs(int node, int per, int dep){
	
	table[0][node] = per;
	depth[node] = dep;
	
	for(edge e : G[node]){
		if(e.to == per) continue;
		dfs(e.to, node, dep+1);
	}
}

void init(int V){
	
	int logV = 1;
	
	for(int i = 1; i <= V; i <<= 1, logV++);
	
	depth.clear();
	depth.resize(V+1);
	table.clear();
	table.resize(logV, vector<int>(V+1,-1));
	
	dfs(1, -1, 0);
	
	for(int k = 0; k + 1 < logV; k++){
		for(int v = 0; v < V; v++){
			if(table[k][v] < 0) table[k+1][v] = -1;
			else table[k+1][v] = table[k][table[k][v]];
		}
	}
}

int lca(int u, int v){
	
	if(depth[u] > depth[v]) swap(u, v);
	for(int k = 0; k < table.size(); k++){
		if((depth[v] - depth[u]) >> k & 1){
			v = table[k][v];
		}
	}
	
	if(u == v) return u; 
	
	for(int k = table.size()-1; k >= 0; k--){
		if(table[k][u] != table[k][v]){
			u = table[k][u];
			v = table[k][v];
		}
	}
	
	return table[0][u];
}

vector<int> cost;

void dfs2(int now = 1, int pre = -1, int sum = 0){
	
	cost[now] = sum;
	
	for(int i = 0; i < G[now].size(); i++){
		if(G[now][i].to == pre) continue;
		
		dfs2(G[now][i].to,now,sum + G[now][i].cost);
	}
}

signed main(){
	// cin.tie(nullptr);
	// ios::sync_with_stdio(false);
	// cout<<fixed<<setprecision(10);
	
	int N, Q;
	// vector<vector<pair<int,int>>> G;
	
	cin>>N;
	
	G.resize(N+1);
	cost.resize(N+1);
	
	for(int i = 0; i < N-1; i++){
		int a, b, c;
		
		cin>>a>>b>>c;
		a++;b++;
		
		G[a].push_back(edge{b,c});
		G[b].push_back(edge{a,c});
		// G[a].push_back(make_pair(b,c));
		// G[b].push_back(make_pair(a,c));
	}
	
	init(N+1);
	dfs2();
	
	cin>>Q;
	
	// for(int i = 1; i <= N; i++){
		// cout<<"i = "<<i-1<<" cost = "<<cost[i]<<endl;
	// }
	
	for(int i = 0; i < Q; i++){
		int a, b, c, ab, bc, ca, abc;
		int sum = 0;
		
		cin>>a>>b>>c;
		a++, b++, c++;
		
		ab = lca(a,b);
		bc = lca(b,c);
		ca = lca(c,a);
		
		abc = lca(ab, c);
		
		// cout<<"ab "<<ab-1<<" bc "<<bc-1<<" ca "<<ca-1<<" abc "<<abc-1<<endl;
		
		sum = cost[a] + cost[b] + cost[c] - cost[ab] - cost[bc] - cost[ca];
		// sum = cost[a] + cost[b] + cost[c] - cost[ab] - cost[bc] - cost[ca] - cost[abc];
		
		cout<<sum<<endl;
	}
	
	
	return 0;
}
/*
7
0 1 1
1 2 2
2 3 3
3 4 4
4 5 5
5 6 6
100

*/
0