不难的题，但是突然就不会分析复杂度了！脑子出了些什么问题。
首先考虑题目中要求一条边恰好经过两次，那么也就是说每进入一个子树，那么就必须把子树内的所有点探索完后再去另一个子树，那么这个问题就显然是可以递归处理的了。
具体来说，对于每一个子树 \(u\)，都存在若条路径 \(u \to v\)，然后当子树合并的时候，相当于从左子树和右子树中选出两条路径 \(u_1 \to v_1, u_2 \to v_2\)，然后合并成 \(u_1 \to v_1 \to u_2 \to v_2\) 的一条路径。
路径最大值最小，考虑二分答案转换成判定性问题。那么我们就可以维护出每个点的所有路径。假设二分的答案为 \(x\)，那么两条路径能够合并的条件是 \(\mathrm{dis}(v_1, u_2) \le x\)，即 \(\mathrm{dep}_{v_1} + \mathrm{dep}_{u_2} \le x + 2 \mathrm{dep}_ {p}\)。
当然，直接维护所有路径肯定不合理，我们考虑删掉一些无用的路径。容易发现，对于一个固定的 \(u\)，我们可以只保留 \(\mathrm{dep}_ v\) 最小的那个，这样每个点处的状态数就是 \(O(\mathrm{siz}_ u)\) 的了，但是这样总状态数还是 \(O(n^2)\) 的。
考虑继续优化。我们先设计上述的状态，设 \(f_{p, u}\) 为 \(p\) 子树内 \(u\) 节点对应的最小的 \(\mathrm{dep}_ v\)，那么转移式子就是 \(f_{p, u} = \min_{\mathrm{dep}_ {v} \le x + 2 \mathrm{dep}_ {p} - \mathrm{dep}_ {u}} f_{lc_p / rc_p, v}\)。我们发现，随着 \(dep_u\) 的增加，这个式子一定是递减的，而递减的就意味着，我们可以只留下那些随着 \(dep_u\) 递增，\(f_u\) 递减的路径。进行这样的操作之后，我们发现，一个点的状态数变为了 \(O(\min(\mathrm{siz}_{lc_u}, \mathrm{siz}_{rc_u}))\)。发现这个复杂度实际上是和启发式合并的复杂度一致的，所以这样总状态数就变成了 \(O(n \log n)\)。
合并的时候直接归并，由于一个状态只会在当前节点与父亲节点被访问一次，所以总复杂度为 \(O(n \log n \log v)\)，\(v\) 为答案的值域。
前面都想到了，但是以为每个点直接归并的复杂度是错的，然后想了一上午，脑瘫达人属于是。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 131200;
typedef long long ll;
int n, fa[MAXN], v[MAXN];
int lc[MAXN], rc[MAXN];
vector<int> e[MAXN];
long long dep[MAXN];
void dfs1(int u, int pre) {
dep[u] = dep[pre] + v[u];
for (int v : e[u]) if (v != pre) {
dfs1(v, u);
if (!lc[u]) lc[u] = v;
else rc[u] = v;
}
}
vector<pair<int, int>> f[MAXN];
int cc = 0;
void dfs2(int u, long long x) {
f[u].clear();
if (!lc[u]) {
f[u].push_back({u, u});
return;
}
dfs2(lc[u], x), dfs2(rc[u], x);
vector<pair<int, int>> L, R, tmp;
auto solve = [&] (vector<pair<int, int>> &L, vector<pair<int, int>> &R) -> vector<pair<int, int>> {
vector<pair<int, int>> res;
int ptr = -1;
for (auto p : L) {
while (ptr + 1 < R.size() && dep[R[ptr + 1].first] <= x + 2 * dep[u] - dep[p.second]) ptr++;
if (ptr >= 0) res.push_back({ p.first, R[ptr].second });
}
return res;
};
L = solve(f[lc[u]], f[rc[u]]), R = solve(f[rc[u]], f[lc[u]]);
tmp.resize(L.size() + R.size());
merge(L.begin(), L.end(), R.begin(), R.end(), tmp.begin(), [&](auto x, auto y) {
return x.first == y.first ? dep[x.second] < dep[y.second] : dep[x.first] < dep[y.first];
});
for (auto p : tmp) {
if (f[u].empty() || dep[f[u].back().second] > dep[p.second]) f[u].push_back(p);
}
}
bool check(long long x) {
dfs2(1, x);
return f[1].size();
}
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%d%d", &fa[i], &v[i]);
e[fa[i]].push_back(i);
}
dfs1(1, 0);
long long l = 0, r = 20000000000;
while (l < r) {
long long mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
printf("%lld\n", l);
return 0;
}