結果

問題 No.1094 木登り / Climbing tree
ユーザー chocoruskchocorusk
提出日時 2020-06-24 02:55:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 742 ms / 2,000 ms
コード長 2,589 bytes
コンパイル時間 1,574 ms
コンパイル使用メモリ 138,496 KB
実行使用メモリ 43,140 KB
最終ジャッジ日時 2024-04-25 18:23:37
合計ジャッジ時間 19,096 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 653 ms
33,032 KB
testcase_02 AC 218 ms
43,140 KB
testcase_03 AC 188 ms
6,944 KB
testcase_04 AC 173 ms
16,256 KB
testcase_05 AC 284 ms
29,228 KB
testcase_06 AC 383 ms
12,544 KB
testcase_07 AC 674 ms
33,028 KB
testcase_08 AC 690 ms
33,236 KB
testcase_09 AC 708 ms
33,276 KB
testcase_10 AC 742 ms
33,132 KB
testcase_11 AC 716 ms
32,988 KB
testcase_12 AC 703 ms
32,968 KB
testcase_13 AC 684 ms
33,048 KB
testcase_14 AC 673 ms
33,152 KB
testcase_15 AC 397 ms
12,032 KB
testcase_16 AC 515 ms
33,408 KB
testcase_17 AC 512 ms
21,504 KB
testcase_18 AC 438 ms
16,768 KB
testcase_19 AC 501 ms
28,684 KB
testcase_20 AC 711 ms
33,140 KB
testcase_21 AC 463 ms
23,728 KB
testcase_22 AC 695 ms
33,204 KB
testcase_23 AC 688 ms
33,088 KB
testcase_24 AC 674 ms
33,096 KB
testcase_25 AC 684 ms
33,008 KB
testcase_26 AC 676 ms
33,124 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
struct HeavyLightDecomposition{
	vector<vector<int>> g;
	vector<int> in, out, rev, cnt, head, par;
	HeavyLightDecomposition(const vector<vector<int>> &g):g(g), in(g.size()), out(g.size()), rev(g.size()), cnt(g.size()), head(g.size()), par(g.size()){}
	void dfs_sz(int x, int p){
		cnt[x]=1, par[x]=p;
		int mx=-1, k=-1;
		for(int i=0; i<g[x].size(); i++){
			int y=g[x][i];
			if(y==p) continue;
			dfs_sz(y, x);
			cnt[x]+=cnt[y];
			if(mx<cnt[y]) mx=cnt[y], k=i;
		}
		if(k>0) swap(g[x][k], g[x][0]);
	}
	void dfs_hld(int x, int p, int &t){
		in[x]=t++;
		rev[in[x]]=x;
		for(int i=0; i<g[x].size(); i++){
			int y=g[x][i];
			if(y==p) continue;
			if(i) head[y]=y;
			else head[y]=head[x];
			dfs_hld(y, x, t);
		}
		out[x]=t;
	}
	void build(){
		int t=0;
		dfs_sz(0, -1);
		dfs_hld(0, -1, t);
	}
	int lca(int u, int v){
		for(; ; v=par[head[v]]){
			if(in[u]>in[v]) swap(u, v);
			if(head[u]==head[v]) return u;
		}
	}
	template<typename F, typename T, typename Q>
	T query(int u, int v, const F &f, const T &e, const Q &q, bool edge=false){//Tの型に注意
		T ret=e;
		for(; ; v=par[head[v]]){
			if(in[u]>in[v]) swap(u, v);
			if(head[u]==head[v]) break;
			ret=f(q(in[head[v]], in[v]+1), ret);
		}
		ret=f(q(in[u]+edge, in[v]+1), ret);
		return ret;
	}
};
int main()
{
    int n;
    cin>>n;
    vector<vector<int>> g(n);
    int a[200020], b[200020], c[200020];
    for(int i=0; i<n-1; i++){
        cin>>a[i]>>b[i]>>c[i];
        a[i]--; b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    HeavyLightDecomposition hld(g);
    hld.build();
    vector<int> v(n+1);
    for(int i=0; i<n-1; i++){
        if(hld.par[b[i]]!=a[i]) swap(a[i], b[i]);
        v[hld.in[b[i]]+1]=c[i];
    }
    for(int i=1; i<=n; i++) v[i]+=v[i-1];
    auto f=[](int x, int y){ return x+y;};
    auto qry=[&](int l, int r){
        return v[r]-v[l];
    };
    int q; cin>>q;
    while(q--){
        int s, t; cin>>s>>t;
        s--; t--;
        cout<<hld.query(s, t, f, 0, qry, true)<<endl;
    }
    return 0;
}
0