結果

問題 No.898 tri-βutree
ユーザー tko919tko919
提出日時 2019-10-05 13:21:56
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,916 bytes
コンパイル時間 1,834 ms
コンパイル使用メモリ 171,652 KB
実行使用メモリ 21,504 KB
最終ジャッジ日時 2024-04-15 16:58:09
合計ジャッジ時間 7,070 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
21,504 KB
testcase_01 AC 4 ms
5,888 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
権限があれば一括ダウンロードができます

ソースコード

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,e.len+d);
    }
}
int 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("%d\n",(dist(x,y)+dist(y,z)+dist(z,x))/2);
    }
    return 0;
}
0