結果

問題 No.1094 木登り / Climbing tree
ユーザー chocorusk
提出日時 2020-06-24 02:55:49
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 1,194 ms / 2,000 ms
コード長 2,589 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,159 ms
コンパイル使用メモリ 135,020 KB
最終ジャッジ日時 2025-01-11 09:50:14
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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