結果

問題 No.898 tri-βutree
ユーザー mugen_1337mugen_1337
提出日時 2020-04-30 14:54:47
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,382 bytes
コンパイル時間 2,429 ms
コンパイル使用メモリ 216,964 KB
実行使用メモリ 31,148 KB
最終ジャッジ日時 2023-08-22 02:42:40
合計ジャッジ時間 13,478 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 231 ms
31,148 KB
testcase_01 AC 1 ms
4,380 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 # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

typedef vector<vector<int>> graph;
struct DoublingLowestCommonAncestor{
    const int LOG;
    vector<int> dep;
    const graph &g;
    //table[i][j]は点jの2^i個上の親情報
    vector<vector<int>> table;
 
    DoublingLowestCommonAncestor(const graph &g):g(g),dep(g.size()),LOG(32-__builtin_clz(g.size())){
        table.assign(LOG,vector<int>(g.size(),-1));
    }
 
    void dfs(int idx,int par,int d){
        //1個上の親の記録
        table[0][idx]=par;
        dep[idx]=d;
        for(auto &to:g[idx]){
            if(to!=par) dfs(to,idx,d+1);
        }
    }
 
    //根としたい点をroot
    void build(int root){
        dfs(root,-1,0);
        for(int k=0;k+1<LOG;k++){
            for(int i=0;i<table[k].size();i++){
                if(table[k][i]==-1) table[k+1][i]=-1;
                else table[k+1][i]=table[k][table[k][i]];
            }
        }
    }
 
    //u,vのlcaを求める
    int query(int u,int v){
        //dep[u]>dep[v]として進める
        if(dep[u]>dep[v]) swap(u,v);
        //深さをそろえる
        for(int i=LOG-1;i>=0;i--){
            if(((dep[v]-dep[u])>>i)&1) v=table[i][v];
        }
        if(u==v) return u;
        for(int i=LOG-1;i>=0;i--){
            if(table[i][u]!=table[i][v]){
                u=table[i][u];
                v=table[i][v];
            }
        }
        return table[0][u];
    }
    
    //呼び出すたびO(logn)
    int dis(int u,int v){
        int p=query(u,v);
        return dep[u]+dep[v]-2*dep[p];
    }
 
    //いるか？これ
    int operator[](const int &k) const{
        return dep[k];
    }
 
    //頂点xのk個上の親を求める。無ければ-1，未verify
    int parent(int x,int k){
        int ret=x;
        int bit=0;
        for(int i=LOG-1;i>=0 and ret>=0;i--){
            if((k>>i)&1) ret=table[i][ret];
        }
        return ret;
    }
};

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    int n;cin>>n;
    vector<vector<int>> g(n);
    vector<vector<pair<int,ll>>> gw(n);

    rep(i,n-1){
        int u,v;ll w;cin>>u>>v>>w;
        g[u].push_back(v);
        g[v].push_back(u);
        gw[u].push_back(make_pair(v,w));
        gw[v].push_back(make_pair(u,w));
    }
    DoublingLowestCommonAncestor lca(g);
    lca.build(0);

    vector<ll> dis(n,0);
    function<void(int,int)> dfs=[&](int pre,int now){
        for(auto &e:gw[now])if(e.first!=pre){
            dis[e.first]=dis[now]+e.second;
            dfs(now,e.first);
        }
    };
    dfs(-1,0);
    int q;cin>>q;
    while(q--){
        int x,y,z;cin>>x>>y>>z;
        ll ans=0;
        ans+=dis[x]+dis[y]+dis[z];
        int par=lca.query(x,y);
        ans-=dis[par]+dis[lca.query(y,z)]+dis[lca.query(z,x)];
        par=lca.query(par,z);
        ans+=dis[par];
        cout<<ans<<endl;
    }

    return 0;
}
0