/* -*- coding: utf-8 -*- * * 1212.cc: No.1212 Second Path - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int BN = 17; const int INF = 1 << 30; /* typedef */ typedef long long ll; typedef queue qi; typedef pair pii; typedef vector vpii; struct Edge { ll sum; int cw, mw0, mw1; bool mwb; Edge(): sum(0), cw(INF), mw0(INF), mw1(INF), mwb(false) {} Edge(ll _sum, int _cw, int _mw0, int _mw1, bool _mwb): sum(_sum), cw(_cw), mw0(_mw0), mw1(_mw1), mwb(_mwb) {} Edge operator+(const Edge &ev) { Edge r; r.sum = sum + ev.sum; r.cw = ev.cw; if (ev.mwb && ev.mw0 == cw) { // not use ev.mw0 if (mw0 < ev.mw1) { r.mw0 = mw0, r.mwb = mwb; r.mw1 = min(mw1, ev.mw1); } else { r.mw0 = ev.mw1, r.mwb = false; r.mw1 = mw0; } } else { if (mw0 < ev.mw0) { r.mw0 = mw0, r.mwb = mwb; r.mw1 = min(mw1, ev.mw0); } else { r.mw0 = ev.mw0, r.mwb = false; r.mw1 = min(mw0, ev.mw1); } } return r; } }; /* global variables */ vpii nbrs[MAX_N]; int ps[MAX_N][BN], ds[MAX_N], cns[MAX_N], mcws[MAX_N][3]; Edge es[MAX_N][BN]; /* subroutines */ inline void setmcw(int mcw[], int w) { for (int i = 0; i < 3; i++) if (mcw[i] > w) { for (int j = 2; j > i; j--) mcw[j] = mcw[j - 1]; mcw[i] = w; break; } } inline int getmcw(int mcw[], int w0, int w1 = INF) { if (mcw[0] != w0) return mcw[0]; if (mcw[1] != w1) return mcw[1]; return mcw[2]; } /* main */ int main() { int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); u--, v--; nbrs[u].push_back(pii(v, w)); nbrs[v].push_back(pii(u, w)); } ps[0][0] = -1, ds[0] = 0; qi q; q.push(0); while (! q.empty()) { int u = q.front(); q.pop(); fill(mcws[u], mcws[u] + 3, INF); int up = ps[u][0], vd = ds[u] + 1; vpii &nbru = nbrs[u]; for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int v = vit->first; if (v != up) { ps[v][0] = u, ds[v] = vd; es[v][0].sum = es[v][0].cw = vit->second; setmcw(mcws[u], vit->second); cns[u]++; q.push(v); } } } for (int u = 0; u < n; u++) { es[u][0].mw0 = mcws[u][0], es[u][0].mwb = true; es[u][0].mw1 = mcws[u][1]; } for (int k = 0; k < BN - 1; k++) for (int u = 0; u < n; u++) { int v = ps[u][k]; if (v >= 0) { ps[u][k + 1] = ps[v][k]; es[u][k + 1] = es[u][k] + es[v][k]; } else ps[u][k + 1] = -1; } int qn; scanf("%d", &qn); while (qn--) { int x, y; scanf("%d%d", &x, &y); x--, y--; ll sum = 0; if (ds[x] > ds[y]) swap(x, y); Edge ex, ey; for (int k = BN - 1; k >= 0; k--) if (((ds[y] - ds[x]) >> k) & 1) { ey = ey + es[y][k]; y = ps[y][k]; } if (x == y) { int minw = min(ey.mw0, min(getmcw(mcws[y], ey.cw), es[y][0].cw)); if (minw >= INF) puts("-1"); else printf("%lld\n", ey.sum + minw * 2); } else { for (int k = BN - 1; k >= 0; k--) if (ps[x][k] != ps[y][k]) { ex = ex + es[x][k]; ey = ey + es[y][k]; x = ps[x][k]; y = ps[y][k]; } ex = ex + es[x][0]; ey = ey + es[y][0]; int z = ps[x][0]; int cw0 = ex.cw, cw1 = ey.cw; if (cw0 > cw1) swap(cw0, cw1); int minw = min(min(ex.mw0, ey.mw0), min(getmcw(mcws[z], cw0, cw1), es[z][0].cw)); if (minw >= INF) puts("-1"); else printf("%lld\n", ex.sum + ey.sum + minw * 2); } } return 0; }