結果
| 問題 | No.1212 Second Path |
| ユーザー |
 chocorusk
|
| 提出日時 | 2020-08-31 00:56:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,069 bytes |
| コンパイル時間 | 2,357 ms |
| コンパイル使用メモリ | 154,888 KB |
| 最終ジャッジ日時 | 2025-01-14 02:13:59 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 9 WA * 32 TLE * 4 |
ソースコード
#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_popcountllusing 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;}};template<typename T>struct SparseTable{using F=function<T(T, T)>;const F f;const T e;vector<vector<T>> spt;vector<int> vlog;SparseTable(const F f, const T &e, const vector<T> &v):f(f), e(e){int b=0, n=v.size();while((1<<b)<=n) b++;spt.resize(b, vector<T>(n));for(int i=0; i<n; i++) spt[0][i]=v[i];for(int i=1; i<b; i++){for(int j=0; j+(1<<i)<=n; j++){spt[i][j]=f(spt[i-1][j], spt[i-1][j+(1<<(i-1))]);}}vlog.resize(n+1);for(int i=2; i<=n; i++) vlog[i]=vlog[i>>1]+1;}T query(int l, int r){int b=vlog[r-l];return f(spt[b][l], spt[b][r-(1<<b)]);}};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];fill(mn, mn+n1, P(INF, INF));for(int i=1; i<n1; i++){int x=par[i];for(int j=0; j<g[x].size(); j++){int y=g[x][j];if(y==i || y==par[x]) continue;mn[i]=minp(mn[i], P(to[x][j], INF));}}vector<P> v(n1);for(int i=0; i<n1; i++) v[hld.in[i]]=mn[i];SparseTable<P> seg(minp, P(INF, INF), v);//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;}