个人感觉官方题解非常成功地割裂了部分分结论和最终做法的关系，堪称一托【】。

这里是一个思路更加自然的题解。（？）

子任务 3 看起来很诡异，我们看看子任务 3。这个 subtask 的内容是判定本来的深度是不是答案。

于是我们本能反应先猜一猜充要条件，看起来好像只要把深度拍到序列上，就是大概这样子

大胆猜测只要我们拍平出一个 $A$ 数组，只要 $A_i \le i + 1$ 就可以了。

交上去喜获 WA。怎么充要条件条件是对每个子树都要这样。于是我们有了一个 $O(N^2)$ 的判定。

于是 subtask 3 是简单的。因为显然，我们把子树调整好后，肯定是延长这个点连向儿子的边——这样才能尽量往后平移，不然你只平移一部分是不优的，这样我们做暴力贪心可以做到 $O(N(N + K))$。

void insert(vi& v, int c, int x) {
	vi ins(c, x);
	v.insert(v.begin(), all(ins));
}
vi dfs(int u) {
	auto [ls, ld] = son[u][0];
	auto [rs, rd] = son[u][1];
	if (!ls) return vi{1};
	vi lhs = dfs(ls), rhs = dfs(rs);
	insert(lhs, ld - 1, 1);
	insert(rhs, rd - 1, 1);
	insert(lhs, max(0, sz(rhs) - sz(lhs)), 1);
	insert(rhs, max(0, sz(lhs) - sz(rhs)), 1);
	vi res(sz(lhs) + 1);
	res[0] = 1;
	L(i, 1, sz(res) - 1) res[i] = lhs[i - 1] + rhs[i - 1];
	int mov = 0;
	L(i, 0, sz(res) - 1) {
		mov = max(mov, res[i] - (i + 1));
	}
	vi ins(mov, 2);
	res.insert(res.begin() + 1, all(ins));
	return res;
}
ll compute_min_depth(int n, vi p, vi c, vi d) {
	L(i, 1, n - 1) {
		son[p[i - 1]][d[i - 1]] = {i, c[i - 1]};
	}
	return sz(dfs(0)) - 1;
}

尝试正解，我们都搞出来这么牛的东西了，肯定是上数据结构优化！

这咋优化？？？我们发现我们要头部插入，支持对位合并，还要求一个 $v_i - i$ 的最小值，看着没啥能很简单做的道理。我们尝试启发式合并维护连续段，但是你发现这好像免不了类似维护分割点外还要维护线段树这种很吃时的东西。

我们观察一下我们的操作有什么性质。头部插入但是尾部没有插入，所以可以类似倒过来维护。然后我们还发现由于我们合并的时候，会先把左右儿子的长度对齐，所以直接线段树合并是没有问题的。线段树合并的时候我们再随便维护一下就可以了。

具体地，为了不搞 tag 什么的东西，我们维护差分数组。这样只有单点修改很方便。线段树合并的时候多传一个已经计算的前缀和，然后进去算一算就可以了。（我是不是写复杂了，其实直接 pushup 就可以了？好像是的，我写了但是懒得改题解了）

void up(int u) {
	sum[u] = sum[ls[u]] + sum[rs[u]];
	maxp[u] = max(maxp[ls[u]], maxp[rs[u]] + sum[ls[u]]);
}
void modify(ll s, ll t, ll k, int &u, ll x) {
	if (!u) u = ++tot;
	if (s == t) {
		sum[u] += x;
		maxp[u] = sum[u] - s;
		return;
	}
	ll mid = (s + t) >> 1;
	if (mid >= k) modify(s, mid, k, ls[u], x);
	else modify(mid + 1, t, k, rs[u], x);
	up(u);
}
ll mov;
int merge(ll s, ll t, int x, int y, ll pre) {
	if (!x | !y) {
		mov = max(mov, pre + max(maxp[x], maxp[y]));
		return x | y;
	}
	if (s == t) {
		sum[x] += sum[y];
		maxp[x] = sum[x] - s;
		mov = max(mov, pre + sum[x] - s);
		return x;
	}
	ll mid = (s + t) >> 1;
	ls[x] = merge(s, mid, ls[x], ls[y], pre);
	rs[x] = merge(mid + 1, t, rs[x], rs[y], pre + sum[ls[x]]);
	return up(x), x;
}

pii son[N][2];
ll len[N];
void insert(int u, ll c, int x) {
	if (!c) return;
	modify(0, inf, inf - len[u], rt[u], -x);
	len[u] += c;
	modify(0, inf, inf - len[u], rt[u], x);
}
void dfs(int u) {
	auto [ls, ld] = son[u][0];
	auto [rs, rd] = son[u][1];
	if (!ls) return modify(0, inf, inf, rt[u], 1);
	dfs(ls), dfs(rs);
	insert(ls, ld - 1, 1);
	insert(rs, rd - 1, 1);
	insert(ls, max(0ll, len[rs] - len[ls]), 1);
	insert(rs, max(0ll, len[ls] - len[rs]), 1);
	mov = -1e18;
	len[u] = len[ls];
	rt[u] = merge(0, inf, rt[ls], rt[rs], 0);
	mov += inf - len[u] - 2;
	insert(u, max(0ll, mov), 2);
	insert(u, 1, 1);
}

ll compute_min_depth(int n, vi p, vi c, vi d) {
	memset(maxp, -0x3f, sizeof maxp);
	L(i, 1, n - 1) {
		son[p[i - 1]][d[i - 1]] = {i, c[i - 1]};
	}
	dfs(0);
	return len[0];
}