难倒不难，128MB 的空间限制快恶心死我了。
我们设 \(d_{u_0,u_1}\) 表示到节点 \((u_0,u_1)\) 距离最近的叶子的距离，这个可以很容易换根 DP 求出。设 \(p_{u_0}\) 表示树 \(u_0\) 中距离最近的两个叶子的距离。设 \(dis(u_0,u_1,v_0,v_1)\)（\(u_0=v_0\)）表示树中两个节点 \(u_1\) 和 \(v_1\) 之间的距离。
（一）若 \(s_0\ne e_0\)，不妨设 \(s_0 < e_0\)。
显然，在第 \(s_0\) 棵树上，从 \((s_0,s_1)\) 花费 \(d_{s_0,s_1}\) 的代价走到最近的叶子是最优的。第 \(e_0\) 棵树同理。对于 \([s_0+1,e_0-1]\) 范围内的树 \(i\)，我们会花费 \(p_i\) 的代价选择最近的两个叶子经过。在两棵树之间传送时，还会产生 \(1\) 的代价。
因此，这种情况的答案为：
\[ans=d_{s_0,s_1}+\sum\limits_{i=s_0+1}^{e_0-1}p_i+d_{e_0,e_1}+(e_0-s_0) \]（二）若 \(s_0=e_0\)。
容易想到树上两点间距离。但这是错的，还可能从 \(s_0\) 走到叶子，传送到相邻的某棵树，经过最近的两个叶子，再传送回来走到 \(e_0\)。
因此，这种情况的答案为：
\[ans=\min\{dis(s_0,s_1,e_0,e_1),d_{s_0,s_1}+p_{s_0-1}+d_{e_0,e_1}+2,d_{s_0,s_1}+p_{s_0+1}+d_{e_0,e_1}+2\} \]你可能会有疑问：万一离 \((s_0,s_1)\) 和 \((e_0,e_1)\) 最近的叶子是同一个，怎么办呢？容易发现，这种情况下从 \((s_0,s_1)\) 和 \((e_0,e_1)\) 分别走到叶子的路径拼起来已经是 \(dis(s_0,s_1,e_0,e_1)\) 了，但还需要经过更多的边，这种情况自然更劣，不会作为 \(\min\) 保留。
时间复杂度 \(O(\sum m_i+q\log\sum m_i)\)。
本题特别卡空间，建议使用树剖 LCA 而不是倍增 LCA，数组能不开 long long 就不要开。
// Problem: P3894 [GDOI2014] 传送
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3894
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;
mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}
const int N = 3.5e5 + 5, M = 1e6 + 5, inf = 1e9 + 10;
const ll Inf = 2e12;
int n, m[N], q, L[N], R[N], dis[M], fa[M], sz[M], son[M], top[M], val[M], dp1[M], dp2[M];
ll near[N];
vector<tuple<int, int>> e[M];
void dfs1(int u, int f, int id) {
fa[u] = f;
sz[u] = 1;
for(auto [v, w] : e[u]) {
if(v != f) {
dis[v] = dis[u] + 1;
val[v] = val[u] + w;
dfs1(v, u, id);
chkmin(near[id], 1LL * dp1[u] + dp1[v] + w);
chkmin(dp1[u], dp1[v] + w);
sz[u] += sz[v];
if(sz[v] > sz[son[u]]) son[u] = v;
}
}
if(!son[u]) dp1[u] = 0;
}
void dfs2(int u, int f, int tp) {
top[u] = tp;
if(!son[u]) return;
for(auto [v, w] : e[u]) {
if(v != f) {
dp2[v] = min(dp1[v], dp2[u] + w);
dfs2(v, u, v == son[u] ? tp : v);
}
}
}
int LCA(int u, int v) {
while(top[u] != top[v]) {
if(dis[top[u]] < dis[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(dis[u] < dis[v]) swap(u, v);
return v;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
rep(i, 1, n) {
cin >> m[i];
L[i] = R[i - 1] + 1;
R[i] = L[i] + m[i] - 1;
rep(j, 1, m[i] - 1) {
int u, v, w;
cin >> u >> v >> w;
e[L[i] + u].emplace_back(L[i] + v, w);
e[L[i] + v].emplace_back(L[i] + u, w);
}
near[i] = Inf;
rep(j, L[i], R[i]) dp1[j] = inf;
dis[L[i]] = 1; val[L[i]] = 0;
dfs1(L[i], 0, i);
if(near[i] >= inf) near[i] = Inf;
near[i] += near[i - 1];
dp2[L[i]] = dp1[L[i]];
dfs2(L[i], 0, L[i]);
}
for(cin >> q; q; --q) {
int x, u, y, v;
cin >> x >> u >> y >> v;
++x; ++y;
if(x > y) swap(x, y), swap(u, v);
u = L[x] + u;
v = L[y] + v;
if(x == y) {
int p = LCA(u, v);
ll ans = val[u] + val[v] - 2 * val[p];
if(x > 1 && near[x - 1] - near[x - 2] < Inf) chkmin(ans, dp2[u] + dp2[v] + (near[x - 1] - near[x - 2]) + 2);
if(x < n && near[x + 1] - near[x] < Inf) chkmin(ans, dp2[u] + dp2[v] + (near[x + 1] - near[x]) + 2);
cout << ans << endl;
}
else {
ll ans = dp2[u] + (near[y - 1] - near[x]) + dp2[v] + (y - x);
cout << (ans >= Inf ? -1 : ans) << endl;
}
}
return 0;
}