結果

問題 No.898 tri-βutree
ユーザー tko919tko919
提出日時 2019-10-05 13:22:40
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 194 ms / 4,000 ms
コード長 1,917 bytes
コンパイル時間 3,468 ms
コンパイル使用メモリ 171,496 KB
実行使用メモリ 21,060 KB
最終ジャッジ日時 2023-08-08 16:17:08
合計ジャッジ時間 7,427 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 86 ms
21,060 KB
testcase_01 AC 3 ms
5,860 KB
testcase_02 AC 4 ms
6,016 KB
testcase_03 AC 3 ms
5,880 KB
testcase_04 AC 4 ms
5,796 KB
testcase_05 AC 4 ms
5,888 KB
testcase_06 AC 3 ms
5,868 KB
testcase_07 AC 185 ms
16,984 KB
testcase_08 AC 186 ms
17,020 KB
testcase_09 AC 186 ms
17,064 KB
testcase_10 AC 187 ms
16,988 KB
testcase_11 AC 188 ms
17,060 KB
testcase_12 AC 190 ms
17,096 KB
testcase_13 AC 185 ms
17,016 KB
testcase_14 AC 190 ms
17,000 KB
testcase_15 AC 186 ms
17,020 KB
testcase_16 AC 191 ms
17,076 KB
testcase_17 AC 189 ms
17,020 KB
testcase_18 AC 190 ms
17,096 KB
testcase_19 AC 188 ms
16,928 KB
testcase_20 AC 194 ms
17,060 KB
testcase_21 AC 187 ms
17,000 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