結果

問題 No.1094 木登り / Climbing tree
ユーザー chocoruskchocorusk
提出日時 2020-06-24 02:55:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 793 ms / 2,000 ms
コード長 2,589 bytes
コンパイル時間 1,980 ms
コンパイル使用メモリ 139,660 KB
実行使用メモリ 43,008 KB
最終ジャッジ日時 2024-11-08 05:52:24
合計ジャッジ時間 21,868 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 793 ms
33,152 KB
testcase_02 AC 236 ms
43,008 KB
testcase_03 AC 206 ms
5,248 KB
testcase_04 AC 199 ms
16,512 KB
testcase_05 AC 335 ms
29,184 KB
testcase_06 AC 425 ms
12,544 KB
testcase_07 AC 786 ms
33,024 KB
testcase_08 AC 784 ms
33,024 KB
testcase_09 AC 793 ms
33,152 KB
testcase_10 AC 780 ms
33,024 KB
testcase_11 AC 789 ms
33,024 KB
testcase_12 AC 772 ms
33,024 KB
testcase_13 AC 777 ms
33,152 KB
testcase_14 AC 769 ms
33,024 KB
testcase_15 AC 426 ms
12,032 KB
testcase_16 AC 572 ms
33,536 KB
testcase_17 AC 490 ms
21,376 KB
testcase_18 AC 465 ms
16,640 KB
testcase_19 AC 547 ms
28,544 KB
testcase_20 AC 774 ms
33,152 KB
testcase_21 AC 504 ms
22,656 KB
testcase_22 AC 764 ms
33,024 KB
testcase_23 AC 743 ms
33,152 KB
testcase_24 AC 746 ms
33,024 KB
testcase_25 AC 739 ms
33,024 KB
testcase_26 AC 743 ms
33,152 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