結果

問題 No.898 tri-βutree
ユーザー tko919tko919
提出日時 2019-10-05 13:22:40
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 177 ms / 4,000 ms
コード長 1,917 bytes
コンパイル時間 1,867 ms
コンパイル使用メモリ 174,800 KB
実行使用メモリ 21,376 KB
最終ジャッジ日時 2024-11-08 22:52:15
合計ジャッジ時間 6,469 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 81 ms
21,376 KB
testcase_01 AC 3 ms
6,016 KB
testcase_02 AC 3 ms
6,016 KB
testcase_03 AC 3 ms
6,144 KB
testcase_04 AC 3 ms
6,016 KB
testcase_05 AC 3 ms
6,016 KB
testcase_06 AC 3 ms
6,016 KB
testcase_07 AC 164 ms
17,408 KB
testcase_08 AC 165 ms
17,280 KB
testcase_09 AC 163 ms
17,280 KB
testcase_10 AC 169 ms
17,408 KB
testcase_11 AC 177 ms
17,280 KB
testcase_12 AC 162 ms
17,280 KB
testcase_13 AC 169 ms
17,280 KB
testcase_14 AC 168 ms
17,280 KB
testcase_15 AC 164 ms
17,408 KB
testcase_16 AC 165 ms
17,408 KB
testcase_17 AC 172 ms
17,280 KB
testcase_18 AC 167 ms
17,408 KB
testcase_19 AC 158 ms
17,280 KB
testcase_20 AC 163 ms
17,280 KB
testcase_21 AC 162 ms
17,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end

struct Edge{ int v,len; };
vector<Edge> g[100010];
int root;
vector<int> parent[17],depth;
void DFS(int v,int p,int d) {
    parent[0][v]=p; depth[v]=d;
    for(Edge u:g[v])if(u.v!=p)DFS(u.v,v,d+1);
}
void init(int V) {
    rep(i,0,17)parent[i].resize(V);
    depth.resize(V,-1); DFS(root,-1,0);
    rep(k,0,16)rep(v,0,V) {
        if(parent[k][v]<0)parent[k+1][v]=-1;
        else parent[k+1][v]=parent[k][parent[k][v]];
    }
}
int lca(int u,int v) {
    if(depth[u]>depth[v]) swap(u,v);
    rep(k,0,17)if((depth[v]-depth[u])>>k&1)v=parent[k][v];
    if(u==v)return u;
    rrep(k,16,-1)if(parent[k][u]!=parent[k][v])u=parent[k][u],v=parent[k][v];
    return parent[0][u];
}
ll path[100010];
void dfs(int v,int pre,ll d){
    path[v]=d;
    if(g[v].empty())return;
    for(Edge e:g[v])if(e.v!=pre){
        dfs(e.v,v,d+e.len);
    }
}
ll dist(int x,int y){
    return path[x]+path[y]-path[lca(x,y)]*2;
}

int main(){
    int n; scanf("%d",&n);
    rep(i,0,n-1){
        int u,v,w; scanf("%d%d%d",&u,&v,&w);
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    } root=0; init(n);
    dfs(0,-1,0);
    int q; scanf("%d",&q);
    rep(rot,0,q){
        int x,y,z; scanf("%d%d%d",&x,&y,&z);
        printf("%lld\n",(dist(x,y)+dist(y,z)+dist(z,x))/2);
    }
    return 0;
}
0