結果

問題 No.898 tri-βutree
ユーザー tarattata1tarattata1
提出日時 2019-10-04 21:55:45
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 181 ms / 4,000 ms
コード長 2,437 bytes
コンパイル時間 2,553 ms
コンパイル使用メモリ 88,588 KB
実行使用メモリ 27,076 KB
最終ジャッジ日時 2023-08-08 15:56:24
合計ジャッジ時間 7,000 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 110 ms
27,076 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 179 ms
17,044 KB
testcase_08 AC 172 ms
17,088 KB
testcase_09 AC 172 ms
17,156 KB
testcase_10 AC 176 ms
16,576 KB
testcase_11 AC 166 ms
17,128 KB
testcase_12 AC 169 ms
17,300 KB
testcase_13 AC 173 ms
16,900 KB
testcase_14 AC 176 ms
17,100 KB
testcase_15 AC 179 ms
17,160 KB
testcase_16 AC 177 ms
16,900 KB
testcase_17 AC 181 ms
17,188 KB
testcase_18 AC 179 ms
17,168 KB
testcase_19 AC 174 ms
17,160 KB
testcase_20 AC 181 ms
17,160 KB
testcase_21 AC 168 ms
16,836 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;


vector<int> vis;
vector<int> depth;
vector<ll> sumw;
vector<vector<pair<int,int> > > g;
vector<vector<int> > anc;

void dfs( int curr, ll currw, vector<int>& vv )
{
    vis[curr]=1;
    depth[curr]=(int)vv.size();
    sumw[curr]=currw;

    int k=1;
    while(k<=depth[curr]) {
        anc[curr].push_back(vv[depth[curr]-k]);
        k*=2;
    }

    vv.push_back( curr );
    int i;
    for(i=0; i<(int)g[curr].size(); i++) {
        if( !vis[g[curr][i].first] ) {
            dfs( g[curr][i].first, currw+g[curr][i].second, vv );
        }
    }
    vv.pop_back();

    return;
}

int getanc( int a, int b )
{
    if(depth[a]>depth[b]) swap(a, b);
    int delta = depth[b]-depth[a];
    int cnt=0;
    while(delta>0) {
        if(delta & (1<<cnt)) {
            b = anc[b][cnt];
            delta -= (1<<cnt);
        }
        cnt++;
    }
    assert(depth[a]==depth[b]);
    if(a==b) return a;

    int N=(int)anc[a].size();
    int i;
    for(i=N-1; i>=0; i--) {
        if((int)anc[a].size()>i) {
            if(anc[a][i]!=anc[b][i]) {
                a = anc[a][i];
                b = anc[b][i];
            }
        }
    }
    return anc[a][0];
}


int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);

    vis.resize(n);
    g.resize(n);
    depth.resize(n);
    sumw.resize(n);
    anc.resize(n);

    int i;
    for(i=0; i<n-1; i++) {
        int a,b,c;
        scanf("%d%d%d", &a, &b, &c);
        g[a].push_back(make_pair(b,c));
        g[b].push_back(make_pair(a,c));
    }

    vector<int> vv;
    dfs(0, 0, vv);


    int Q;
    scanf("%d", &Q);
    int q;
    for(q=0; q<Q; q++) {
        int x,y,z;
        scanf("%d%d%d", &x, &y, &z);

        ll ans = sumw[x] + sumw[y] + sumw[z];
        int tmp0=getanc(x,y);
        int tmp1=getanc(y,z);
        int tmp2=getanc(z,x);
        ll ans0 = sumw[tmp0]+sumw[tmp1]+sumw[tmp2];
        ans = ans - ans0;
        printf("%lld\n", ans);
    }

    return 0;
}
0