結果

問題 No.898 tri-βutree
ユーザー ゆにぽけゆにぽけ
提出日時 2023-10-26 11:10:48
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 250 ms / 4,000 ms
コード長 4,149 bytes
コンパイル時間 1,852 ms
コンパイル使用メモリ 144,176 KB
実行使用メモリ 27,008 KB
最終ジャッジ日時 2024-09-25 12:19:52
合計ジャッジ時間 9,237 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 103 ms
27,008 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 223 ms
22,408 KB
testcase_08 AC 229 ms
22,396 KB
testcase_09 AC 215 ms
22,516 KB
testcase_10 AC 223 ms
22,272 KB
testcase_11 AC 223 ms
22,400 KB
testcase_12 AC 230 ms
22,400 KB
testcase_13 AC 222 ms
22,400 KB
testcase_14 AC 225 ms
22,272 KB
testcase_15 AC 224 ms
22,308 KB
testcase_16 AC 250 ms
22,400 KB
testcase_17 AC 235 ms
22,400 KB
testcase_18 AC 218 ms
22,272 KB
testcase_19 AC 236 ms
22,400 KB
testcase_20 AC 231 ms
22,380 KB
testcase_21 AC 228 ms
22,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cassert>
#include<cmath>
#include<ctime>
#include<iomanip>
#include<numeric>
#include<stack>
#include<queue>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<bitset>
#include<random>
#include<functional>
#include<utility>
using namespace std;

struct Edge{
    int to; // 行き先
    long wei; // 重み

    Edge(int to,long wei = 1):to(to),wei(wei) {}
};

using Graph = vector<vector<Edge>>;

struct Tree{
    private:
    int n;
    template<class T> inline bool chmax(T &a,T b){if(a < b){a = b; return true;} return false;}

    public:
    vector<vector<int>> par; // par[i][j] -> 頂点iから2^j個だけ登った頂点
    vector<int> depth; // 根からの深さ
    vector<long> Wdepth; // 根からの重み付き深さ
    vector<int> subtree; //その頂点を根とした部分木(自身も含む)の大きさ

    Tree(const Graph &G,int root = 0) {init(G,root);}

    void init(const Graph &G,int root = 0)
    {
        n = (int)G.size();
        int k = 1;

        while((1 << k) < n) k++; // n以上の最小の2の冪の指数だけ確保しておけば最悪の場合も根には辿り着ける

        par.assign(n,vector<int>(k,-1)); // -1はそれ以上登れないことを示す
        depth.assign(n,-1);
        Wdepth.assign(n,-1);
        subtree.assign(n,0);

        DFS(G,root,-1,0);

        for(int j = 0;j+1 < k;j++){
            for(int i = 0;i < n;i++){
                // 2^j個登ってはみ出るなら当然2^(j+1)登ってもはみ出る
                if(par[i][j] < 0){
                    par[i][j+1] = -1;
                }else{ // 2^(j+1)登る = 2^j登ってさらに2^j登る
                    par[i][j+1] = par[par[i][j]][j];
                }
            }
        }
    }

    // DFSで深さを求める
    int DFS(const Graph &G,int v,int p,int d,long w = 1)
    {
        par[v][0] = p;
        depth[v] = d;
        Wdepth[v] = w;

        int res = 1;

        for(auto e:G[v]){
            if(e.to == p) continue;

            res += DFS(G,e.to,v,d + 1,w + e.wei);
        }

        return subtree[v] = res;
    }

    // 最小共通祖先
    int lca(int u,int v)
    {
        assert(0 <= u && u < n && 0 <= v && v < n);

        if(depth[u] < depth[v]) swap(u,v);
        int k = (int)par[0].size();

        // 深さの差を2の冪で埋めていく
        for(int j = 0;j < k;j++){
            if((depth[u]-depth[v]) & 1 << j) u = par[u][j];
        }

        // そこで出会う場合
        if(u == v) return u;

        // 真上にlcaがいる状態まで進む
        for(int j = k-1;j >= 0;j--){
            if(par[u][j] != par[v][j]){
                u = par[u][j];
                v = par[v][j];
            }
        }

        // 真上を返す
        return par[u][0];
    }

    // 頂点uとvの最短距離を返す
    int dist(int u,int v)
    {
        int x = lca(u,v);
        return depth[u] + depth[v] - 2*depth[x];
    }

    // 頂点uとvの重み付き最短距離を返す
    long Wdist(int u,int v)
    {
        int x = lca(u,v);
        return Wdepth[u] + Wdepth[v] - 2*Wdepth[x];
    }

    // 頂点xが頂点uとvの最短路上にいるかどうか
    bool onpath(int u,int v,int x)
    {
        return dist(u,x) + dist(x,v) == dist(u,v);
    }

    // 木の直径を返す
    int diameter()
    {
        int ret = -1;
        int u;
        for(int v = 0;v < n;v++) if(chmax(ret,dist(0,v))) u = v;

        ret = -1;
        for(int v = 0;v < n;v++) chmax(ret,dist(u,v));

        return ret;
    }
};
int N;
void solve()
{
	cin >> N;
	Graph G(N);
	for(int i = 1;i < N;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		G[u].push_back(Edge(v,w));
		G[v].push_back(Edge(u,w));
	}
	Tree T(G);
	int Q;
	cin >> Q;
	for(;Q--;)
	{
		int x[3];
		for(int i = 0;i < 3;i++) cin >> x[i];
		long long ans = 0;
		for(int i = 0;i < 3;i++) ans += T.Wdist(x[i],x[(i+1)%3]);
		ans /= 2;
		cout << ans << "\n";
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int tt = 1;
	//cin >> tt;
	while(tt--) solve();
}
0