結果

問題 No.898 tri-βutree
ユーザー snow39snow39
提出日時 2019-10-04 22:14:44
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 552 ms / 4,000 ms
コード長 2,283 bytes
コンパイル時間 1,076 ms
コンパイル使用メモリ 98,680 KB
実行使用メモリ 31,232 KB
最終ジャッジ日時 2024-04-26 08:37:56
合計ジャッジ時間 11,553 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 326 ms
31,232 KB
testcase_01 AC 5 ms
8,320 KB
testcase_02 AC 5 ms
8,448 KB
testcase_03 AC 6 ms
8,320 KB
testcase_04 AC 5 ms
8,320 KB
testcase_05 AC 6 ms
8,320 KB
testcase_06 AC 5 ms
8,320 KB
testcase_07 AC 512 ms
25,472 KB
testcase_08 AC 521 ms
25,600 KB
testcase_09 AC 512 ms
25,728 KB
testcase_10 AC 517 ms
25,600 KB
testcase_11 AC 498 ms
25,600 KB
testcase_12 AC 517 ms
25,600 KB
testcase_13 AC 517 ms
25,472 KB
testcase_14 AC 529 ms
25,472 KB
testcase_15 AC 510 ms
25,728 KB
testcase_16 AC 514 ms
25,600 KB
testcase_17 AC 552 ms
25,472 KB
testcase_18 AC 541 ms
25,472 KB
testcase_19 AC 509 ms
25,472 KB
testcase_20 AC 506 ms
25,728 KB
testcase_21 AC 507 ms
25,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

//入力
const int MAX_V=100010;
const int MAX_LOG_V=20;
vector<int> G[MAX_V];  //グラフの隣接リスト表現
int root;              //根ノードの番号

int parent[MAX_LOG_V][MAX_V];  //親を2^k回辿って到達する頂点（根を通り過ぎる場合は-1）
int depth[MAX_V];  //根からの深さ

void dfs(int v,int p,int d){
  parent[0][v]=p;
  depth[v]=d;
  for(int i=0;i<G[v].size();i++){
    if(G[v][i]!=p) dfs(G[v][i],v,d+1);
  }
}

//初期化
void init(int V){
  //parent[0]とdepthを初期化する
  dfs(root,-1,0);
  //parentを初期化する
  for(int k=0;k+1<MAX_LOG_V;k++){
    for(int v=0;v<V;v++){
      if(parent[k][v]<0) parent[k+1][v]=-1;
      else parent[k+1][v]=parent[k][parent[k][v]];
    }
  }
}

//uとvのLCAを求める
int lca(int u,int v){
  //uとvの深さが同じになるまで親を辿る
  if(depth[u]>depth[v]) swap(u,v);
  for(int k=0;k<MAX_LOG_V;k++){
    if((depth[v]-depth[u])>>k&1){
      v=parent[k][v];
    }
  }
  if(u==v) return u;
  //二分探索でLCAを求める
  for(int k=MAX_LOG_V-1;k>=0;k--){
    if(parent[k][u]!=parent[k][v]){
      u=parent[k][u];
      v=parent[k][v];
    }
  }
  return parent[0][u];
}

ll val[100010];

int N;
vector<pair<int,ll>> g[100010];

void setVal(int now,int par,ll v){
  val[now]=v;
  for(int i=0;i<g[now].size();i++){
    int nex=g[now][i].first;
    ll c=g[now][i].second;

    if(nex==par) continue;
    setVal(nex,now,v+c);
  }
}


int main(){
  cin>>N;
  rep(i,N-1){
    int a,b,c;
    cin>>a>>b>>c;
    g[a].push_back(mkp(b,c));
    g[b].push_back(mkp(a,c));

    G[a].push_back(b);
    G[b].push_back(a);
  }

  root=0;
  init(N);

  setVal(0,-1,0ll);

  int Q;
  cin>>Q;
  for(int i=0;i<Q;i++){
    int x,y,z;
    cin>>x>>y>>z;

    ll ans=val[x]+val[y]+val[z];
    int u=lca(x,y);
    int v=lca(x,z);
    int w=lca(z,y);
    ans-=(val[u]+val[v]+val[w]);
    int p=lca(u,z);
    //ans+=val[p];

    cout<<ans<<endl;
  }

  return 0;
}
0