結果

問題 No.898 tri-βutree
ユーザー leaf_1415leaf_1415
提出日時 2019-10-04 21:37:36
言語 C++11
(gcc 13.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,473 bytes
コンパイル時間 1,127 ms
コンパイル使用メモリ 61,412 KB
実行使用メモリ 26,056 KB
最終ジャッジ日時 2024-11-08 21:55:22
合計ジャッジ時間 5,950 ms
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 20 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#define llint long long
using namespace std;
struct edge{
llint to, cost;
edge(){}
edge(llint a, llint b){
to = a, cost = b;
}
};
llint n, Q;
vector<edge> G[100005];
int Prev[100005][17];
int depth[100005];
llint dist[100005];
int getLCA(int u, int v){
int x = u, y = v;
if(depth[y] > depth[x]) swap(x, y);
for(int i = 16; i >= 0; i--){
if(depth[x] - (1<<i) >= depth[y]) x = Prev[x][i];
}
if(x == y) return x;
for(int i = 16; i >= 0; i--){
if(Prev[x][i] != Prev[y][i]){
x = Prev[x][i];
y = Prev[y][i];
}
}
x = Prev[x][0];
return x;
}
void dfs(int v, int p, int d, llint dst)
{
Prev[v][0] = p, depth[v] = d, dist[v] = dst;
for(int i = 0; i < G[v].size(); i++){
if(G[v][i].to == p) continue;
dfs(G[v][i].to, v, d+1, dst + G[v][i].cost);
}
}
llint calc(llint s, llint t)
{
llint lca = getLCA(s, t);
return dist[s] + dist[t] - 2 * dist[lca];
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
llint u, v, w;
for(int i = 1; i <= n-1; i++){
cin >> u >> v >> w;
u++, v++;
G[u].push_back(edge(v, w));
G[v].push_back(edge(u, w));
}
dfs(1, -1, 0, 0);
for(int i = 1; i < 16; i++){
for(int j = 1; j <= n; j++){
Prev[j][i] = Prev[Prev[j][i-1]][i-1];
}
}
cin >> Q;
llint x, y, z;
for(int q = 0; q < Q; q++){
cin >> x >> y >> z;
x++, y++, z++;
llint ans = calc(x, y) + calc(y, z) + calc(z, x);
cout << ans / 2 << "\n";
}
flush(cout);
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0