結果

問題 No.898 tri-βutree
ユーザー snow39
提出日時 2019-10-04 22:14:44
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 476 ms / 4,000 ms
コード長 2,283 bytes
コンパイル時間 927 ms
コンパイル使用メモリ 99,236 KB
実行使用メモリ 31,232 KB
最終ジャッジ日時 2024-11-08 22:16:59
合計ジャッジ時間 10,470 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

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