verify/range_edge_graph.test.cpp

• View this file on GitHub
• Last update: 2025-02-20 17:16:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/4022

Depends on

• HLD (Algorithm/hld.hpp)
• 区間に辺を貼るテク (Datastructure/range_edge_graph.hpp)
• verify用テンプレート (Utility/template.hpp)

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/4022"
#include "../Utility/template.hpp"
#include "../Datastructure/range_edge_graph.hpp"
#include "../Algorithm/hld.hpp"

using pll = pair<int, ll>;
int main() {
	ll N, s, t;
	cin >> N >> s >> t;
	s--, t--;
	vec<vec<pll>> g(N);
	vec<vec<int>> ng(N);
	rep(i, 0, N-1) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		g[a].push_back(pll(b, c));
		g[b].push_back(pll(a, c));
		ng[a].push_back(b);
		ng[b].push_back(a);
	}

	vec<int> T(N), D(N);
	rep(i, 1, N) {
		cin >> T[i] >> D[i];
	}

	HLD hld(ng, 0);
	ng.clear();

	vec<int> ord(N, -1);
	vec<vec<pll>> ds(N);


	{   
		int id = 0;
		queue<int> que;
		que.push(0);
		ord[0] = id++;

		while(!que.empty()) {
			auto now = que.front();
			que.pop();
			ds[hld.dep[now]].push_back(pll(ord[now], now));

			for(auto [to, c] : g[now]) if(ord[to] == -1) {
				ord[to] = id++;
				que.push(to);
			}
		}

		rep(i, 0, N) sort(all(ds[i]));
	}

    
	vec<int> rev(N);
	rep(i, 0, N) {
		rep(j, 0, ds[i].size()) {
			rev[ds[i][j].second] = j;
		}
	}

	range_edge_graph gh(N);


	rep(i, 1, N) {//辺を貼るフェーズ
	    ll d = D[i];
		auto& vs = ds[hld.dep[i]];
		//自分がvsの中で m 番目とする。
		int m = rev[i];
		int l, r;
		{
			int li = 0;
			int ri = m;
			while(li < ri) {//xxxxooo
				int mid = (li + ri) >> 1;
				int dis = hld.dist(vs[mid].second, i);
				if(dis <= d) ri = mid;
				else li = mid + 1;
			}
			l = li;
		}


		{
			int li = m;
			int ri = vs.size()-1;
			while(li < ri) {
				int mid = (li + ri + 1) >> 1;
				int dis = hld.dist(vs[mid].second, i);
				if(dis <= d) li = mid;
				else ri = mid - 1;
			}
			r = li;
		}

		//[l, r]
		l = vs[l].first;
		r = vs[r].first;//ordに変換
		int now = ord[i];

		gh.add_edge(now, now+1, l, r+1, T[i], LLONG_MAX);
	}

	rep(i, 0, N) {
		int now = ord[i];
		for(auto [to, c] : g[i]) {
			to = ord[to];
			gh.add_edge(now, to, c, LLONG_MAX);

		}
	}

	auto G = gh.graph();
	int M = G.size();

	s = ord[s], t = ord[t];
	vec<ll> ans(M, LLONG_MAX);
	ans[s] = 0;



	priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> que;
	que.push({0, s});
	while(!que.empty()) {
		auto [c, v] = que.top();
		que.pop();
		if(ans[v] < c) continue;
		for(auto e : G[v]) {
			ll cost = e.cost + ans[v];
			if(chmin(ans[e.to], cost)) {
				que.push({ans[e.to], e.to});
			}

		}
	}

	cout << ans[t] << endl;




	





}

#line 1 "verify/range_edge_graph.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/problems/4022"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/range_edge_graph.hpp"
struct range_edge_graph {
    #define pb push_back
    struct edge {
        int to;
        ll cost;
        //ll cap; フローならこれも使う。
        edge(){}
        edge(int a, ll b, ll c) : to(a), cost(b) {}
        //edge(int a, ll b, ll c) : to(a), cost(b), cap(c) {}
        //フローの時のコンストラクタ
    };

    edge e(int to) {
        return edge(to, 0, LLONG_MAX/4);
    }
  
    int n;
    int sz = 1;
    int node;
    vec<vec<edge>> g;

    range_edge_graph(int N) : n(N) {
        while(sz < n) sz <<= 1;

        g = vec<vec<edge>>(n + 4 * sz);
        node = n + 4 * sz;

        rep(i, 1, sz) {
            g[i + n].pb( e(i * 2 + n) );
            g[i + n].pb( e(i * 2 + 1 + n) );

            g[i * 2 + n + 2 * sz].pb( e(i + n + 2 * sz) );
            g[i * 2 + 1 + n + 2 * sz].pb( e(i + n + 2 * sz) );
        }

        rep(i, 0, n) {
            g[i + n + sz].pb( e(i) );
            g[i].pb( e(i + n + 3 * sz) );
        }
    }

    void add_edge(int sl, int sr, int tl, int tr, ll cost, ll cap) {
        int nw = node++;
        int nw2 = node++;
        g.pb({ edge( nw2, cost, cap ) });
        g.pb(vec<edge>());

        sl += sz;
        sr += sz;
        while(sl < sr) {
            if(sl & 1) g[sl + n + 2 * sz].pb( e(nw) ), sl++;
            if(sr & 1) sr--, g[sr + n + 2 * sz].pb( e(nw) );
            sl >>= 1; sr >>= 1;
        }

        tl += sz;
        tr += sz;
        while(tl < tr) {
            if(tl & 1) g[nw2].pb( e(tl + n) ), tl++;
            if(tr & 1) tr--, g[nw2].pb( e(tr + n) ); 
            tl >>= 1, tr >>= 1;
        }
    }

    void add_edge(int s, int t, ll cost, ll cap) {
        g[s].pb( edge(t, cost, cap) );
    }

    vec<vec<edge>> graph() {
        return g;
    }

    #undef pb
};

/*
@brief 区間に辺を貼るテク
@docs doc/range_edge_graph.md
*/
#line 1 "Algorithm/hld.hpp"
struct HLD {
    using vi = vec<int>;
    using pi = pair<int, int>;
    using pll = pair<long long, long long>;
    vi in, out, par, root, rev, dep, pre_vs;
    vec<ll> dep_w;
    //          親/成分のtop/inの中身→頂点番号
    int n, r;  // 頂点数、根
    
    static vec<vec<int>> extract_graph(const vec<vec<pll>> &G) {
        vec<vec<int>> g(G.size());
        for (int i = 0; i < int(G.size()); i++) {
            for (auto [w, to] : G[i])
                if (i < to) {
                    g[i].push_back(to);
                    g[to].push_back(i);
                }
        }
        return g;
    }
    HLD(const vec<vec<pll>> &g, int a) : HLD(extract_graph(g), a) {
        auto dfs = [&](auto f, int v) -> void {
            for (auto [w, to] : g[v])
                if (to != par[v]) {
                    dep_w[to] = dep_w[v] + w;
                    f(f, to);
                }
        };
        dfs(dfs, r);
    }

    HLD(vec<vi> g, int a) : n(g.size()), r(a) {
        vi siz(n, 0);
        in = out = root = rev = vi(n);
        par = vi(n, -1);
        dep = vi(n, 0);
        dep_w = vec<ll>(n, 0);
        root[r] = r;

        auto dfs_siz = [&](auto f, int v) -> void {
            siz[v]++;
            for (int &to : g[v])
                if (to != par[v]) {
                    dep[to] = dep[v] + 1;
                    par[to] = v;
                    f(f, to);
                    siz[v] += siz[to];
                    if (siz[to] > siz[g[v][0]] || g[v][0] == par[v])
                        swap(to, g[v][0]);
                }
            return;
        };

        dfs_siz(dfs_siz, r);

        int t = 0;

        auto dfs_hld = [&](auto f, int v) -> void {
            rev[t] = v;
            in[v] = t++;
            for (int to : g[v])
                if (to != par[v]) {
                    root[to] = (to == g[v][0] ? root[v] : to);
                    f(f, to);
                }
            out[v] = t;
        };

        dfs_hld(dfs_hld, r);
        for (int i = 0; i < n; i++) dep_w[i] = dep[i];
    }

    // 以下、欲しいもののみ書く

    int operator()(int v) const { return in[v]; }
    int operator()(int u, int v) const {
        assert(par[u] == v || par[v] == u);
        if(par[u] == v) return in[u];
        else return in[v];
    }

    int lca(int a, int b) {
        while (1) {
            if (in[a] > in[b]) swap(a, b);
            if (root[a] == root[b]) return a;
            b = par[root[b]];
        }
    }

    ll dist(int a, int b) {
        int lc = lca(a, b);
        return dep_w[a] + dep_w[b] - 2 * dep_w[lc];
    }

    vec<pi> path(int s, int t, bool edge) {
        vec<pi> ls, rs;
        while (root[s] != root[t]) {
            if (dep[root[s]] > dep[root[t]]) {
                ls.emplace_back(in[s] + 1, in[root[s]]);  // 上り
                s = par[root[s]];
            } else {
                rs.emplace_back(in[root[t]], in[t] + 1);  // 下り
                t = par[root[t]];
            }
        }

        if (dep[s] > dep[t])
            ls.emplace_back(in[s] + 1, in[t] + edge);  // 上り
        else
            rs.emplace_back(in[s] + edge, in[t] + 1);  // 下り

        reverse(all(rs));
        for (auto &p : rs) ls.push_back(p);
        return ls;
    }

    pi subtree(int u, bool edge) { return pi(in[u] + edge, out[u]); }

    int kth_ancestor(int v, int k) {
        if (k > dep[v]) return -1;
        while (v >= 0) {
            if (k <= dep[v] - dep[root[v]]) {
                return rev[in[v] - k];
            } else {
                k -= dep[v] - dep[root[v]] + 1;
                v = par[root[v]];
            }
        }
    }

    int jump(int s, int t, int k) {
        int m = lca(s, t);
        int le = dep[s] - dep[m];
        int ri = dep[t] - dep[m];
        if (0 <= k && k <= le + ri) {
            if (k < le)
                return kth_ancestor(s, k);
            else
                return kth_ancestor(t, le + ri - k);
        }
        return -1;
    }

    int aux_tree(vi vs, vec<vi> &g) {
        if (vs.empty()) return -1;

        auto cmp = [&](int i, int j) { return in[i] < in[j]; };
        sort(all(vs), cmp);
        int m = vs.size();

        rep(i, 0, m - 1) vs.push_back(lca(vs[i], vs[i + 1]));
        sort(all(vs), cmp);
        vs.erase(unique(all(vs)), vs.end());

        vi st;
        for (auto v : vs) {
            while (st.size()) {
                int p = st.back();
                if (in[p] < in[v] && in[v] < out[p]) break;
                st.pop_back();
            }
            if (st.size()) {
                g[st.back()].push_back(v);
                g[v].push_back(st.back());
            }
            st.push_back(v);
        }

        swap(vs, pre_vs);
        return pre_vs[0];
    }

    void clean(vec<vi> &g) {
        for (auto v : pre_vs) g[v] = vi();
        pre_vs = vi();
        return;
    }
};
/*
@brief HLD
@docs doc/hld.md
*/
#line 5 "verify/range_edge_graph.test.cpp"

using pll = pair<int, ll>;
int main() {
	ll N, s, t;
	cin >> N >> s >> t;
	s--, t--;
	vec<vec<pll>> g(N);
	vec<vec<int>> ng(N);
	rep(i, 0, N-1) {
		ll a, b, c;
		cin >> a >> b >> c;
		a--, b--;
		g[a].push_back(pll(b, c));
		g[b].push_back(pll(a, c));
		ng[a].push_back(b);
		ng[b].push_back(a);
	}

	vec<int> T(N), D(N);
	rep(i, 1, N) {
		cin >> T[i] >> D[i];
	}

	HLD hld(ng, 0);
	ng.clear();

	vec<int> ord(N, -1);
	vec<vec<pll>> ds(N);


	{   
		int id = 0;
		queue<int> que;
		que.push(0);
		ord[0] = id++;

		while(!que.empty()) {
			auto now = que.front();
			que.pop();
			ds[hld.dep[now]].push_back(pll(ord[now], now));

			for(auto [to, c] : g[now]) if(ord[to] == -1) {
				ord[to] = id++;
				que.push(to);
			}
		}

		rep(i, 0, N) sort(all(ds[i]));
	}

    
	vec<int> rev(N);
	rep(i, 0, N) {
		rep(j, 0, ds[i].size()) {
			rev[ds[i][j].second] = j;
		}
	}

	range_edge_graph gh(N);


	rep(i, 1, N) {//辺を貼るフェーズ
	    ll d = D[i];
		auto& vs = ds[hld.dep[i]];
		//自分がvsの中で m 番目とする。
		int m = rev[i];
		int l, r;
		{
			int li = 0;
			int ri = m;
			while(li < ri) {//xxxxooo
				int mid = (li + ri) >> 1;
				int dis = hld.dist(vs[mid].second, i);
				if(dis <= d) ri = mid;
				else li = mid + 1;
			}
			l = li;
		}


		{
			int li = m;
			int ri = vs.size()-1;
			while(li < ri) {
				int mid = (li + ri + 1) >> 1;
				int dis = hld.dist(vs[mid].second, i);
				if(dis <= d) li = mid;
				else ri = mid - 1;
			}
			r = li;
		}

		//[l, r]
		l = vs[l].first;
		r = vs[r].first;//ordに変換
		int now = ord[i];

		gh.add_edge(now, now+1, l, r+1, T[i], LLONG_MAX);
	}

	rep(i, 0, N) {
		int now = ord[i];
		for(auto [to, c] : g[i]) {
			to = ord[to];
			gh.add_edge(now, to, c, LLONG_MAX);

		}
	}

	auto G = gh.graph();
	int M = G.size();

	s = ord[s], t = ord[t];
	vec<ll> ans(M, LLONG_MAX);
	ans[s] = 0;



	priority_queue<array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> que;
	que.push({0, s});
	while(!que.empty()) {
		auto [c, v] = que.top();
		que.pop();
		if(ans[v] < c) continue;
		for(auto e : G[v]) {
			ll cost = e.cost + ans[v];
			if(chmin(ans[e.to], cost)) {
				que.push({ans[e.to], e.to});
			}

		}
	}

	cout << ans[t] << endl;




	





}

Back to top page