考虑倍增。类似 SA，$f_{i,j}$ 表示从 $i$ 开始走 $2^j$ 步，每次走最大的边，最后得到的答案排名是多少。每次排序以 $f_{i,j-1}$ 为第一关键字，$\max_{v \in g_{i,j-1}} f_{v,j-1}$ 为第二关键字。其中 $g_{i,j-1}$ 表示能使得以 $i$ 为起点的字典序最大的路径的所有可能的结束点，用 bitset 维护。

复杂度瓶颈是 $\mathcal O(\frac{n^3 \log K}{\omega})$。能过。

:::success[Code]

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2026;

int n;
int mx[N];
vector<int> g[N];
int f[N];		// 从 i 开始走 2^j 步，排名（从小到大）
int sum[N], mus[N];
bitset<N> b[N];		// 可能的结束点
bitset<N> tmp[N];
int nums[N], cnt;
int rk[N], pre[N], sa[N];
vector<int> cur;
int res;

vector<int> get(bitset<N> a) {
	vector<int> res;
	for (int i = 1; i <= n + 1; ++ i )
		if (a[i]) res.push_back(i);
	return res;
}

int calculate_diamonds(signed n, signed m, signed k, std::vector<signed> U, std::vector<signed> V, std::vector<signed> D) {
	::n = n;
	for (int i = 0; i < m; ++ i ) {
		int u = U[i], v = V[i], w = D[i];
		u ++, v ++ ;
		if (w > mx[u]) {
			mx[u] = w;
			g[u] = {v};
		} else if (w == mx[u]) {
			g[u].push_back(v);
		}
	}
	mx[n + 1] = 1e9 + 1;
	for (int i = 1; i <= n; ++ i ) g[n + 1].push_back(i);
	k ++ ;
	
	for (int i = 1; i <= n + 1; ++ i ) nums[ ++ cnt] = mx[i];
	sort(nums + 1, nums + cnt + 1);
	cnt = unique(nums + 1, nums + cnt + 1) - nums - 1;
	for (int i = 1; i <= n + 1; ++ i ) {
		int w = lower_bound(nums + 1, nums + cnt + 1, mx[i]) - nums;
		f[i] = w;
		for (int v : g[i]) b[i][v] = 1;
		sum[i] = mx[i];
	}
	
	cur.push_back(n + 1);
	for (int j = 0; j < 31; ++ j ) {
		if (k >> j & 1) {
			int mx = 0;
			bitset<N> nxt;
			int ans = 0;
			for (int u : cur) {
				if (f[u] > mx) {
					mx = f[u];
					nxt = b[u];
					ans = sum[u];
				} else if (f[u] == mx) {
					nxt |= b[u];
				}
			}
			cur.clear();
			res += ans;
			for (int i = 1; i <= n + 1; ++ i )
				if (nxt[i]) cur.push_back(i);
		}
		
		for (int i = 1; i <= n + 1; ++ i ) {
			tmp[i].reset();
			mus[i] = 0;
			pre[i] = 0;
			int mx = 0;
			for (int v : get(b[i]))
				if (f[v] > mx) {
					mx = f[v];
					tmp[i] = b[v];
					mus[i] = sum[v];
				} else if (f[v] == mx) {
					tmp[i] |= b[v];
					assert(mus[i] == sum[v]);
				}
			pre[i] = mx;
		}
		
		iota(rk + 1, rk + n + 2, 1);
		sort(rk + 1, rk + n + 2,
			[&](int x, int y) {
				if (f[x] != f[y]) return f[x] < f[y];
				return pre[x] < pre[y];
			});
		
		for (int i = 1; i <= n + 1; ++ i ) {
			sum[i] += mus[i];
			b[i] = tmp[i];
		}
		
		for (int i = 1, j = 0; i <= n + 1; ++ i ) {
			if (i == 1 || (f[rk[i]] != f[rk[i - 1]] ? f[rk[i]] > f[rk[i - 1]] : pre[rk[i]] > pre[rk[i - 1]])) {
				j ++ ;
			}
			sa[rk[i]] = j;
		}
		
		for (int i = 1; i <= n + 1; ++ i ) f[i] = sa[i];
	}
	
	return res - ((int)1e9 + 1);
}

:::