結果

問題 No.898 tri-βutree
ユーザー CinnamorollCinnamoroll
提出日時 2019-10-05 00:06:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 349 ms / 4,000 ms
コード長 7,372 bytes
コンパイル時間 1,980 ms
コンパイル使用メモリ 181,100 KB
実行使用メモリ 40,832 KB
最終ジャッジ日時 2024-11-08 22:38:51
合計ジャッジ時間 9,410 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 110 ms
40,832 KB
testcase_01 AC 4 ms
6,400 KB
testcase_02 AC 4 ms
6,528 KB
testcase_03 AC 4 ms
6,528 KB
testcase_04 AC 4 ms
6,528 KB
testcase_05 AC 5 ms
6,400 KB
testcase_06 AC 4 ms
6,528 KB
testcase_07 AC 332 ms
37,400 KB
testcase_08 AC 334 ms
37,504 KB
testcase_09 AC 339 ms
37,376 KB
testcase_10 AC 340 ms
37,376 KB
testcase_11 AC 330 ms
37,504 KB
testcase_12 AC 327 ms
37,504 KB
testcase_13 AC 332 ms
37,376 KB
testcase_14 AC 332 ms
37,500 KB
testcase_15 AC 323 ms
37,376 KB
testcase_16 AC 330 ms
37,376 KB
testcase_17 AC 325 ms
37,376 KB
testcase_18 AC 339 ms
37,376 KB
testcase_19 AC 349 ms
37,376 KB
testcase_20 AC 327 ms
37,504 KB
testcase_21 AC 336 ms
37,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// warm heart, wagging tail,and a smile just for you!
//                                                                     ███████████
//                                                                   ███╬╬╬╬╬╬╬╬╬╬███
//                                                                ███╬╬╬╬╬████╬╬╬╬╬╬███
//                                            ███████████       ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
//                                      █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
//                               ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
//                             ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
//                           ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
//                         ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
//                       ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
//                     ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
//                 ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
//     █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
//   ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
//   ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
//       ██████████████  ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
//                         ███████                           █████  ███████████████████  
//
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

struct LCA{
  int N;
  vector<int> dist;
  vector<vector<int>> edge,par;
  int MAX_LOG_V;

  LCA(const vector<vector<int>> &edge) : edge(edge){
    N = edge.size();
    dist.resize(N);
    MAX_LOG_V = log2(N)+1;
    par.resize(MAX_LOG_V);
    REP(i,MAX_LOG_V) par[i].resize(N);
  };

  void dfs(int no,int p,int d){
    par[0][no]=p;
    dist[no]=d;
    for(auto to:edge[no]){
      if(to!=p) dfs(to,no,d+1);
    }
  }

  void init(){
    dfs(0,-1,0); //root,parent,dist
    for(int k=0;k+1<MAX_LOG_V;++k){
      for(int v=0;v<N;v++){
        if(par[k][v]<0) par[k+1][v]=-1;
        else par[k+1][v]=par[k][par[k][v]];
      }
    }
  }

  int get(int u,int v){
    if(dist[u]>dist[v]) swap(u,v);
    for(int k=0;k<MAX_LOG_V;++k){
      if((dist[v]-dist[u])>>k&1){
        v=par[k][v];
      }
    }
    if(u==v) return u;
    for(int k=MAX_LOG_V-1;k>=0;--k){
      if(par[k][u]!=par[k][v]){
        u=par[k][u];
        v=par[k][v];
      }
    }
    return par[0][u];
  }

  bool isTrail(int x, int y, int z){
    return dist[x]+dist[z]-dist[get(x,z)]*2 == dist[x]+dist[y]*2+dist[z]-dist[get(x,y)]*2-dist[get(y,z)]*2;
  }
};

const int N = 1e5+10;
vector<P> edge[N];
vec dist(N,0);

void dfs(int no, int par){
  for(P to:edge[no]){
    if(to.fs==par) continue;
    dist[to.fs] = dist[no]+to.sc;
    dfs(to.fs,no);
  }
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;

  mat tmp(n);
  REP(_,n-1){
    int x,y,c;
    cin >> x >> y >> c;
    tmp[x].emplace_back(y);
    tmp[y].emplace_back(x);
    edge[x].emplace_back(y,c);
    edge[y].emplace_back(x,c);
  }

  LCA lca(tmp); lca.init();
  dfs(0,-1);

  int q;
  cin >> q;

  REP(_,q){
    int x,y,z;
    cin >> x >> y >> z; 
    
    cout << dist[x]+dist[y]+dist[z]-dist[lca.get(x,y)]-dist[lca.get(y,z)]-dist[lca.get(z,x)] << "\n";
  }

  return 0;
}
0