結果

問題 No.898 tri-βutree
ユーザー mugen_1337mugen_1337
提出日時 2020-04-30 15:05:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 410 ms / 4,000 ms
コード長 3,497 bytes
コンパイル時間 2,823 ms
コンパイル使用メモリ 218,388 KB
実行使用メモリ 32,972 KB
最終ジャッジ日時 2024-11-08 23:41:39
合計ジャッジ時間 11,591 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 233 ms
32,972 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 406 ms
24,176 KB
testcase_08 AC 410 ms
24,304 KB
testcase_09 AC 391 ms
24,180 KB
testcase_10 AC 389 ms
24,052 KB
testcase_11 AC 388 ms
24,172 KB
testcase_12 AC 393 ms
24,160 KB
testcase_13 AC 386 ms
24,104 KB
testcase_14 AC 397 ms
24,176 KB
testcase_15 AC 383 ms
24,176 KB
testcase_16 AC 381 ms
24,168 KB
testcase_17 AC 397 ms
24,172 KB
testcase_18 AC 389 ms
24,300 KB
testcase_19 AC 394 ms
24,176 KB
testcase_20 AC 398 ms
24,176 KB
testcase_21 AC 391 ms
24,176 KB
権限があれば一括ダウンロードができます

ソースコード

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;
        int pxy=lca.query(x,y);
        int pyz=lca.query(y,z);
        int pzx=lca.query(z,x);
        int p=lca.query(pxy,z);
        ll a=dis[x]-dis[p];
        ll b=dis[y]-dis[p];
        ll c=dis[z]-dis[p];
        ll ab=dis[pxy]-dis[p];
        ll bc=dis[pyz]-dis[p];
        ll ca=dis[pzx]-dis[p];
        cout<<a+b+c-ab-bc-ca<<endl;
    }

    return 0;
}
0