結果

問題 No.898 tri-βutree
コンテスト
ユーザー auaua
提出日時 2019-10-04 22:38:32
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,299 bytes
コンパイル時間 1,978 ms
コンパイル使用メモリ 165,484 KB
実行使用メモリ 30,720 KB
最終ジャッジ日時 2024-11-08 22:21:55
合計ジャッジ時間 13,089 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
vector<vector<pll> >G(100010);
vector<pll>par(100010);
vector<ll>dis(100010);
void dfs(ll i,ll p,ll d,ll def){
    par[i].first=p;
    par[i].second=def-1;
    dis[i]=d;
    rep(j,G[i].size()){
        if(G[i][j].first==p)continue;
        dfs(G[i][j].first,i,d+G[i][j].second,def+1);
    }
}
ll LCA(ll x,ll y){
    ll s=par[x].second+1;
    ll t=par[y].second+1;
    if(t>s){
        return LCA(x,par[y].first);
    }else if(t<s){
        return LCA(par[x].first,y);
    }else{
        if(x==y)return x;
        else return LCA(par[x].first,par[y].first);
    }
}
int main(){
    ll n;
    cin>>n;
    rep(i,n-1){
        ll u,v,w;
        cin>>u>>v>>w;
        G[u].pb(mp(v,w));
        G[v].pb(mp(u,w));
    }
    dfs(0LL,(ll)-1,0LL,0LL);
    ll q;
    cin>>q;
    while(q){
        ll x,y,z;
        cin>>x>>y>>z;
        cout<<dis[x]+dis[y]+dis[z]-dis[LCA(x,y)]-dis[LCA(y,z)]-dis[LCA(z,x)]<<'\n';
        q--;
    }
}
0