結果

問題 No.1212 Second Path
ユーザー chocoruskchocorusk
提出日時 2020-08-31 01:22:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 647 ms / 3,000 ms
コード長 5,535 bytes
コンパイル時間 2,326 ms
コンパイル使用メモリ 159,640 KB
実行使用メモリ 78,708 KB
最終ジャッジ日時 2024-11-15 16:12:14
合計ジャッジ時間 26,599 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 413 ms
53,940 KB
testcase_01 AC 515 ms
54,232 KB
testcase_02 AC 508 ms
53,156 KB
testcase_03 AC 520 ms
54,340 KB
testcase_04 AC 512 ms
51,052 KB
testcase_05 AC 524 ms
51,396 KB
testcase_06 AC 602 ms
78,676 KB
testcase_07 AC 631 ms
64,956 KB
testcase_08 AC 633 ms
65,700 KB
testcase_09 AC 628 ms
65,540 KB
testcase_10 AC 602 ms
64,548 KB
testcase_11 AC 619 ms
65,004 KB
testcase_12 AC 621 ms
65,484 KB
testcase_13 AC 630 ms
66,040 KB
testcase_14 AC 638 ms
64,320 KB
testcase_15 AC 647 ms
64,944 KB
testcase_16 AC 632 ms
64,680 KB
testcase_17 AC 398 ms
54,708 KB
testcase_18 AC 173 ms
14,440 KB
testcase_19 AC 168 ms
14,184 KB
testcase_20 AC 174 ms
14,820 KB
testcase_21 AC 177 ms
15,700 KB
testcase_22 AC 169 ms
14,440 KB
testcase_23 AC 158 ms
14,680 KB
testcase_24 AC 158 ms
14,428 KB
testcase_25 AC 157 ms
14,684 KB
testcase_26 AC 164 ms
14,300 KB
testcase_27 AC 166 ms
14,936 KB
testcase_28 AC 161 ms
15,700 KB
testcase_29 AC 462 ms
55,068 KB
testcase_30 AC 464 ms
53,980 KB
testcase_31 AC 461 ms
54,876 KB
testcase_32 AC 539 ms
49,360 KB
testcase_33 AC 460 ms
42,608 KB
testcase_34 AC 602 ms
62,912 KB
testcase_35 AC 251 ms
18,632 KB
testcase_36 AC 521 ms
51,136 KB
testcase_37 AC 506 ms
48,112 KB
testcase_38 AC 528 ms
49,460 KB
testcase_39 AC 399 ms
33,488 KB
testcase_40 AC 198 ms
15,244 KB
testcase_41 AC 525 ms
49,936 KB
testcase_42 AC 5 ms
14,808 KB
testcase_43 AC 5 ms
14,560 KB
testcase_44 AC 6 ms
15,192 KB
testcase_45 AC 588 ms
78,584 KB
testcase_46 AC 590 ms
78,708 KB
testcase_47 AC 598 ms
78,688 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>
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
template<typename Monoid>
struct SegmentTree{
	using F=function<Monoid(Monoid, Monoid)>;
	int sz;
	vector<Monoid> seg;
	const F f;
	const Monoid e;

	SegmentTree(int n, const F f, const Monoid &e): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
	}

	SegmentTree(int n, const F f, const Monoid &e, vector<Monoid> v): f(f), e(e){
		sz=1;
		while(sz<n) sz<<=1;
		seg.resize(2*sz, e);
		for(int i=0; i<n; i++) seg[i+sz]=v[i];
		for(int i=sz-1; i>=1; i--){
			seg[i]=f(seg[2*i], seg[2*i+1]);
		}
	}

	void update(int k, const Monoid &x){
		k+=sz;
		seg[k]=x;
		while(k>1){
			k>>=1;
			seg[k]=f(seg[2*k], seg[2*k+1]);
		}
	}

	Monoid query(int a, int b){
		a+=sz, b+=sz;
		Monoid retl=e, retr=e;
		for(;a<b; a>>=1, b>>=1){
			if(b&1) retr=f(seg[--b], retr);
			if(a&1) retl=f(retl, seg[a++]);
		}
		return f(retl, retr);
	}

	Monoid operator[](const int &k) const{
		return seg[k+sz];
	}
};
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(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(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 dfs2(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];
			dfs2(y, x, t);
		}
		out[x]=t;
	}
	void build(){
		int t=0;
		dfs(0, -1);
		dfs2(0, -1, t);
	}
	int la(int v, int k){
		while(1){
			int u=head[v];
			if(in[v]-k>=in[u]) return rev[in[v]-k];
			k-=in[v]-in[u]+1;
			v=par[u];
		}
	}
	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){
		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], in[v]+1), ret);
		return ret;
	}
};
int main()
{
	int n; cin>>n;
	vector<vector<int>> g(n);
	vector<vector<ll>> to(n);
	for(int i=0; i<n-1; i++){
		int u, v;
		ll w;
		cin>>u>>v>>w;
		u--; v--;
		g[u].push_back(v);
		g[v].push_back(u);
		to[u].push_back(w);
		to[v].push_back(w);
	}
	int n1=n;
	for(int i=1; i<n; i++){
		if(g[i].size()==1){
			n1++;
		}
	}
	const ll INF=1e9+7;
	g.resize(n1);
	to.resize(n1);
	n1=n;
	for(int i=1; i<n; i++){
		if(g[i].size()==1){
			g[i].push_back(n1);
			g[n1].push_back(i);
			to[i].push_back(INF);
			to[n1].push_back(INF);
			n1++;
		}
	}
	auto minp=[](P a, P b){
		if(a.first>b.first) swap(a, b);
		return P(a.first, min(b.first, a.second));
	};
	HeavyLightDecomposition hld(g);
	hld.build();
	ll s[200020], wp[200020];
	int d[200020];
	int par[200020];
	par[0]=-1, s[0]=0, d[0]=0, wp[0]=INF;
	auto dfs=[&](auto dfs, int x, int p)->void{
		for(int i=0; i<g[x].size(); i++){
			int y=g[x][i];
			if(y==p){
				wp[x]=to[x][i];
				par[x]=y;
			}else{
				s[y]=s[x]+to[x][i];
				d[y]=d[x]+1;
				dfs(dfs, y, x);
			}
		}
	};
	dfs(dfs, 0, -1);
	P mn[200020];
	multiset<ll> st[100010];
	for(int x=0; x<n; x++){
		for(int i=0; i<g[x].size(); i++){
			if(g[x][i]!=par[x]) st[x].insert(to[x][i]);
		}
	}
	fill(mn, mn+n1, P(INF, INF));
	for(int i=1; i<n1; i++){
		int x=par[i];
		st[x].erase(st[x].lower_bound(wp[i]));
		if(st[x].size()==1){
			mn[i].first=*st[x].begin();
		}else if(st[x].size()){
			auto itr=st[x].begin();
			mn[i].first=*itr;
			itr++;
			mn[i].second=*itr;
		}
		st[x].insert(wp[i]);
	}
	vector<P> v(n1);
	for(int i=0; i<n1; i++) v[hld.in[i]]=mn[i];
	SegmentTree<P> seg(n1, minp, P(INF, INF), v);
	auto qr=[&](int l, int r){ return seg.query(l, r);};
	auto solve1=[&](int x, int p, int p1){
		int x1=g[x].back();
		ll w1=to[x].back();
		if(x1==par[x]){
			x1=g[x][0];
			w1=to[x][0];
		}
		return minp(hld.query(x1, p1, minp, P(INF, INF), qr), P(w1, INF));
	};
	auto solve=[&](int x, int y){
		int p=hld.lca(x, y);
		if(p==x){
			int p1=hld.la(y, d[y]-d[p]-1);
			ll myon=min(solve1(y, p, p1).first, wp[p]);
			if(myon==INF) return -1ll;
			else return s[y]-s[p]+2*myon;
		}else if(p==y){
			int p1=hld.la(x, d[x]-d[p]-1);
			ll myon=min(solve1(x, p, p1).first, wp[p]);
			if(myon==INF) return -1ll;
			else return s[x]-s[p]+2*myon;
		}
		int p1=hld.la(x, d[x]-d[p]-1), p2=hld.la(y, d[y]-d[p]-1);
		P mn1=solve1(x, p, p1), mn2=solve1(y, p, p2);
		ll mn0=mn1.first;
		if(mn1.first==wp[p2]) mn0=mn1.second;
		if(mn2.first==wp[p1]) mn0=min(mn0, mn2.second);
		else mn0=min(mn0, mn2.first);
		mn0=min(mn0, wp[p]);
		if(mn0==INF) return -1ll;
		else return s[x]+s[y]-2*s[p]+2*mn0;
	};
	int q; cin>>q;
	while(q--){
		int x, y; cin>>x>>y;
		x--; y--;
		printf("%lld\n", solve(x, y));
	}
	return 0;
}
0