摸底考试 #1

T1 三值的排序

写一个程序计算出，给定的一个 $1,2,3$ 组成的数字序列，使用交换操作，排成升序所需的最少交换次数。

贪心：http://112.36.16.166:88/submission/48004

T2 日记

日记之中，写满了质数，两个质数之间如果没有其他质数，那么则称为相邻的质数。 给定 $N, k$ ，询问不超过 $N$ 的数中能够表示成连续的 $k$ 个质数之和的最大的数是多 少?

欧拉筛预处理素数然后直接暴力。

代码实现：http://112.36.16.166:88/submission/39019

T3 分蛋糕

分析

环形区间 DP，按照套路，把环复制一份。

设 $f_{l,r}$ 表示区间 $i$ 到 $j$，小 $Y$ 先手获得的最大贡献，转移就是小 $Y$ 的两种决策，然后确定小 $Z$ 的决策，转移即可，通过记忆化搜索实现较为容易，时间复杂度 $O(n^2)$。

T4 街灯

题目难度：普及+/提高

塔立于都市，攀登上塔，能够到达更远的地方。但是上塔，需要破解谜题。 有 $N$ 个数，但不给你，而是给了你 $\frac{N\times(N-1)}{2}$ 个数，代表它们两两的和。 那么，这 $N$ 个数是多少呢？

分析

先将读入的数字排序，显然最小值是 $a_1+a_2$，次小值 $a_1+a_3$。然后枚举 $a_2+a_3$ 的值，这样子就可以解出来 $a_1, a_2, a_3$。

在读入的数字中将 $a_1+a_2, a_2+a_3, a_1+a_3$ 删除，则剩下的数字最小的一定是 $a_1+a_4$ ，于是我们可以解出当前情况下的 $a_4$ 了。以此类推，就可以解出 $a_5, a_6 \dots$。

用一个 multiset 来快速实现加数和删数，注意到如果 $sum_i = sum_i - 1, i >3$，那么如果 $sum_{i-1}$ 能形成一组解，那么 $sum_i$ 也能形成一组与原来相同的解，可以特判或者用 unique​ 去重。

代码实现

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 100010;

multiset<int> st;
int n, a[N], s[N];
vector<vector<int> > ans;
stack<int> stk;

void solve() {
	while (stk.size()) st.insert(stk.top()), stk.pop();
	for (int i = 1; i <= 3; i ++ ) {
		for (int j = i + 1; j <= 3; j ++ ) {
			st.erase(st.find(a[i] + a[j]));
			stk.push(a[i] + a[j]);
		}
	}
	for (int i = 4; i <= n; i ++ ) {
		int x = (*st.begin()) - a[1];
		if (x < a[i - 1]) return;
		for (int j = 1; j <= i - 1; j ++ ) {
			int sum = x + a[j];
			if (st.find(sum) == st.end()) return;
			st.erase(st.find(sum));
			stk.push(sum);
		}
		a[i] = x;
	}
	vector<int> vt;
	for (int i = 1; i <= n; i ++ ) vt.push_back(a[i]);
	ans.push_back(vector<int>(n, 0));
}

signed main() {
	n = read();
	int tot = n * (n - 1) / 2;
	for (int i = 1; i <= tot; i ++ ) s[i] = read(), st.insert(s[i]);
	sort(s + 1, s + tot + 1);
	for (int i = 3; i <= n; i ++ ) {
		int t = s[1] + s[2] + s[i];
		if (t & 1) continue;
		int x = t / 2;
		a[1] = x - s[i], a[2] = s[1] - a[1], a[3] = s[2] - a[1];
		if (a[1] <= 0) continue;
		solve();
	}
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i ++ ) {
		for (int j = 0; j < ans[i].size(); j ++ ) {
			printf("%d ", ans[i][j]);
		}
		puts("");
	}
	return 0;
}

NOIP 训练赛 #1

T3 智能小球

简要题意：给你一张带权完全图，初始时（时刻为 $0$）小 $k$ 会选择一个节点并放置一个点，之后每个时刻，这个点会随机移动到其他节点处，初始时小 $k$ 选择第 $i$ 个节点的概率为 $p_i$。

如果在 $t$ 时刻点在节点 $i$ 的位置，那么它移动到节点 $j$ 的概率为：

$$\frac{dist(i, j)}{\sum_{k \ne i} dist(i, k)}$$

其中 $dist(i, j)$ 表示节点 $i$ 到节点 $j$ 最短路径的长度。

给出 $T$，求出在这个时刻点在每个节点的概率。

分析

考虑朴素 DP，设 $f_{t, i}$ 表示转移到时刻 $t$ 当前在 $i$ 点的概率，那么 $f_{t,i}=f_{t,i}+f_{t-1,j} \times dist(i, j) \ {\div \ sum_j}$。

使用 $floyd$ 可以快速求出两点之间的最短路径，我们提前预处理出 $sum_j$，转移的时间复杂度为 $O(1)$，但是仍然需要枚举 $t,i,j$，综上，这个 DP 的时间复杂度为 $O(tn^2+n^3)$。

这个 DP 式子一看就很像矩阵快速幂能优化的东西，结合 $T \le 1e9$，基本可以确定是矩阵快速幂优化 DP。

设矩阵 $F$ 表示一个 $1 \times n$ 的矩阵，矩阵 $Mat$ 表示 $n \times n$ 的转移矩阵，那么原来的 $dist(i, j) \ {\div \ sum_j}$ 就是转移矩阵上的系数。

用矩阵快速幂的时候，是从一个状态推到另一个状态，所以将 $sum_j$ 改为 $sum_i$。

代码实现

#include <bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 202;

int n, hyl;
int g[N][N], sum[N];
double p[N];

struct Matrix {
	double a[N][N];
	Matrix() {
		for (int i = 0; i <= n; i ++ ) {
			for (int j = 0; j <= n; j ++ ) {
				a[i][j] = 0;
			}
		}
	}
	Matrix operator * (const Matrix &b) const {
		Matrix res;
		for (int i = 1; i <= n; i ++ ) {
			for (int k = 1; k <= n; k ++ ) {
				for (int j = 1; j <= n; j ++ ) {
					res.a[i][j] += a[i][k] * b.a[k][j];
				}
			}
		}
		return res;
	} 
} mat, f;

Matrix qpow(Matrix a, int b) {
	Matrix res = a; b -- ;
	for (; b; b >>= 1) {
		if (b & 1) res = res * a;
		a = a * a;
	}
	return res;
}

signed main() {
	n = read(), hyl = read();
	for (int i = 1; i <= n; i ++ ) scanf("%lf", &p[i]);
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= n; j ++ ) {
			g[i][j] = read();
		}
	}
	for (int k = 1; k <= n; k ++ ) {
		for (int i = 1; i <= n; i ++ ) {
			for (int j = 1; j <= n; j ++ ) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= n; j ++ ) {
			sum[i] += g[i][j];
		}
	}
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= n; j ++ ) {
			mat.a[i][j] = (double)g[i][j] / sum[i];
		}
	} 
	for (int i = 1; i <= n; i ++ ) f.a[1][i] = p[i];
	Matrix ans = f * qpow(mat, hyl);
	for (int i = 1; i <= n; i ++ ) printf("%.6lf\n", ans.a[1][i]);
	return 0;
}

NOIP 训练赛 #2

T4 顽皮的猴子

分析

对于 $50 \%$ 的数据，就是求路径上的最小值，直接倍增即可。

对于 $100 \%$ 的数据，用队列维护路径上的前 $k$ 小值，仿照上面的做法即可。

代码实现

50 pts：http://112.36.16.166:88/submission/42557

#include <bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 100010, M = 2 * N;

int n, m, q;
int h[N], e[M], ne[M], idx;
int dep[N], f[N][25];
bool vis[N];

class Queue {
public:
	int q[15], ql = 1, qr = 0;
	void push(int x) { q[ ++ qr] = x; }
	int size() { return qr - ql + 1; }
	int front() { return q[ql]; }
	int back() { return q[qr]; }
	int pop() { ql ++ ; }
	int clear() { ql = 1, qr = 0; }
} g[N][25], c[N];

void add(int a, int b) {
	e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

Queue merge(Queue a, Queue b, int k) {
	Queue res;
	while ((a.size() || b.size()) && res.size() < k) {
		if (a.size() && b.size()) {
			if (a.front() < b.front()) res.push(a.front()), a.pop();
			else res.push(b.front()), b.pop();
		}
		else if (!a.size()) res.push(b.front()), b.pop();
		else if (!b.size()) res.push(a.front()), a.pop();
	}
	return res;
}

void bfs(int st) {
	queue<int> q;
	q.push(st);
	dep[st] = 1;
	vis[st] = true;
	while (q.size()) {
		auto t = q.front(); q.pop();
		for (int i = h[t]; i; i = ne[i]) {
			int j = e[i];
			if (vis[j]) continue;
			vis[j] = true;
			dep[j] = dep[t] + 1;
			f[j][0] = t;
			g[j][0] = c[t];
			for (int k = 1; k <= 21; k ++ ) {
				int fa = f[j][k - 1];
				f[j][k] = f[fa][k - 1];
				g[j][k] = merge(g[j][k - 1], g[fa][k - 1], 10);
			}
			q.push(j);
		}
	}
}

Queue getmin(int a, int b, int k) {
	if (dep[a] < dep[b]) swap(a, b);
	int d = dep[a] - dep[b];
	Queue res = c[a];
	for (int i = 0; i <= 21; i ++ ) {
		if (d >> i & 1) {
			res = merge(res, g[a][i], k);
			a = f[a][i];
		}
	}
	if (a == b) return res;
	res = merge(res, c[b], k);
	for (int i = 21; i >= 0; i -- ) {
		if (f[a][i] == f[b][i]) continue;
		res = merge(res, g[a][i], k);
		res = merge(res, g[b][i], k);
		a = f[a][i], b = f[b][i];
	}
	res = merge(res, g[a][0], k);
	return res;
}

signed main() {
	n = read(), m = read(), q = read();
	for (int i = 1; i < n; i ++ ) {
		int a = read(), b = read();
		add(a, b), add(b, a);
	}
	for (int i = 1; i <= m; i ++ ) {
		int live_ = read();
		c[live_].push(i);
	}
	bfs(1);
	while (q -- ) {
		int a = read(), b = read(), k = read();
		Queue ans = getmin(a, b, k);
		if (ans.size() == 0) puts("0");
		else {
			printf("%d ", min(k, ans.size()));
			for (int i = ans.ql; i <= ans.qr; i ++ ) printf("%d ", ans.q[i]);
			puts("");
		}
	}
	return 0;
}

NOIP 训练赛 #4

T4 简单题（PYYZ-2330）

这题单独写过：PYYZOJ-2186

小 $H$ 要用 $n+1$ 只骡子运送 $k$ 种物资。每只骡子可以任选物资运输（也可以选择运
输 $0$ 种物资）。
由于骡子并不是马，所以没有任何一种物资能够同时被第 $0\sim n-1$ 只这 $n$ 只骡子
运输。
由于骡子并不是马，所以第 $1 \sim n$ 这只骡子并不能运输全部的 $k$ 种物资。
根据以上原则，一共有多少种运输方案？

请给出答案对 $10^9+7$ 取模的结果。

对于所有数据，满足 $0 \le T \le 10^5, 3 \le n,k \le 10^8$。

分析

根据套路，我们可以将题目转化为网格图上的问题。

考虑题目要求 2，可以转化为至少有一列 $[1 \sim n]$ 全为 $0$ 的段，我们单独考虑。

对于剩下的情况，我们需要满足的性质：

• $[1 \sim n]$ 中至少有一个 $1$（避免与全 $0$ 重复）
• $[0 \sim n-1]$ 中至少有一个 $0$（题目要求 1）

---

---

由此我们可以得到式子：

---

然而这个式子直接做是 $O(k)$ 的，所以我们考虑化简。

发现这个式子长得很像二项式定理，考虑用二项式定理优化：

$$\sum_{i=1}^k\binom{k}{i} \times 2^i \times [(2^{n-1}-2)\times 4 + 2 + 2] ^ {k-i}$$

$$\sum_{i=1}^k\binom{k}{i} \times 2^i \times [(2^{n-1}-1)\times 4] ^ {k-i}$$

$$\sum_{i=1}^k\binom{k}{i} \times 2^i \times (2^{n+1}-4) ^ {k-i}$$

为了使用二项式定理，可以化为：

$$[\sum_{i=0}^k\binom{k}{i} \times 2^i \times (2^{n+1}-4) ^ {k-i}]-(2^{n+1}-4)^{k}$$

根据二项式定理，可化简为下面式子：

$$(2^{n+1}-2)^{k}-(2^{n+1}-4)^{k}$$

使用快速幂可以在 $O(\log_2 k)$ 的时间复杂度内解决本题。

代码很简单：

#include <bits/stdc++.h>

using namespace std;

#define int long long

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    return x * f;
}

const int mod = 1e9 + 7;

int qpow(int a, int b) {
    int res = 1 % mod;
    for (; b; b >>= 1) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
    }
    return res;
}

signed main() {
    int _ = read();
    while (_ -- ) {
        int n = read(), k = read();
        int a = qpow(qpow(2, n + 1) - 2, k);
        int b = qpow(qpow(2, n + 1) - 4, k);
        printf("%lld\n", (a - b + mod) % mod);
    }
    return 0;
}

NOIP 训练赛 #6

T4 简单题（PYYZ-2330）

题目难度：提高+/省选-

简要题意，给你一张 $n$ 个点 $m$ 条边的无向图，计算如果一条边能成为最小生成树上的边可以达到的最大边权。

对于 $75 \%$ 的数据， $N, M \leq 8000$。
对于 $100\%$ 的数据， $1 \leq N \leq 10^5, N-1 \leq M \leq 10^6, 0 \leq w_i \leq 10^9$。

分析

定义一条路径的代价 $cost_{u,v}$ 为 $u$ 点到达 $v$ 点路径上最大边权的最小值。

对于每条边的最大费用，答案为删除这条边后，这条边的两个端点的代价。

所以对于 $75\%$ 的数据，可以直接跑 $Dijkstra$，即把原先判断是否满足三角不等式的 $dist_v > dist_u + w$ 更改为 $dist_v > max\{dist_u, w\}$，这也是满足 $Dijkstra$ 的贪心性质的。

当然也可以跑 $Kruskal$ 重构树来得到这 $75pts$（最小瓶颈路）。

对于 $100\%$ 的数据，使用最小生成树，显然对于一条边有两种情况：

• 对于非树边，一条非树边如果要成为树边，那么边权最大是树上两点之间路径上的最大边权。

  • 直接树上倍增即可。

• 对于树边，删除这条边后，最小生成树会变成两个连通块，如果这条边依然是树边，那么它的边权必须要 $\leq$ 连接两个联通块边集中边权的最小值（不然可以通过另一条路径连接两个联通块且代价更小）。

  • 用非树边去更新每条树边的权值，这显然可以用树剖来做，下面是倍增的做法（zpl 太强啦）。

  • 设 $h_{i,j}$ 表示 $i$ 点到其 $2^{j}$ 级祖先的答案。

  • 考虑一种类似 $lazytag$ 的做法，每次倍增跳祖先，并在跳的过程中更新 $h_{i, j}$，做完后 $pushdown$ 下传标记。

void modify(int a, int b, int c) {
	if (dep[a] < dep[b]) swap(a, b);
	int d = dep[a] - dep[b], res = 0;
	for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? lazy[a][i] = min(lazy[a][i], c), a = f[a][i] : 0;
	if (a == b) return;
	for (int i = 18; i >= 0; i -- ) {
		if (f[a][i] == f[b][i]) continue;
		lazy[a][i] = min(lazy[a][i], c);
		lazy[b][i] = min(lazy[b][i], c);
		a = f[a][i], b = f[b][i];
	}
	lazy[a][0] = min(lazy[a][0], c);
	lazy[b][0] = min(lazy[b][0], c);
}

void pushdown() {
	for (int k = 18; k; k -- ) {
		for (int i = 1; i <= n; i ++ ) {
			lazy[i][k - 1] = min(lazy[i][k - 1], lazy[i][k]);
			lazy[f[i][k - 1]][k - 1] = min(lazy[f[i][k - 1]][k - 1], lazy[i][k]);
		}
	}
}

代码实现

Dijkstra（75 pts）

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

inline string readstr() {
	string s = ""; char ch = getchar();
	for (; isspace(ch); ch = getchar());
	for (; !isspace(ch); ch = getchar()) s.push_back(ch);
	return s;
}

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') << 1;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 100010, M = 20 * N;

int n, m, dist[N];
int h[N], w[M], e[M], ne[M], idx = 1;
bool del[M], vis[N];

void add(int a, int b, int c) {
	e[ ++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

void dijkstra(int st) {
	fill(dist, dist + n + 1, 1000000000);
	memset(vis, 0, sizeof vis);
	priority_queue<PII, vector<PII>, greater<PII>> q;
	q.emplace(0, st);
	dist[st] = 0;
	while (q.size()) {
		auto t = q.top(); q.pop();
		int u = t.second;
		if (vis[u]) continue;
		vis[u] = true;
		for (int i = h[u]; i; i = ne[i]) {
			if (del[i]) continue;
			int j = e[i];
			if (dist[j] > max(dist[u], w[i])) {
				dist[j] = max(dist[u], w[i]);
				q.emplace(dist[j], j);
			}
		}
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i ++ ) {
		int a = read(), b = read(), c = read();
		add(a, b, c), add(b, a, c);
	}
	for (int i = 2; i <= idx; i += 2) {
		del[i] = del[i ^ 1] = true;
		dijkstra(e[i]);
		printf("%d\n", dist[e[i ^ 1]]);
		del[i] = del[i ^ 1] = false;
	} 
	return 0;
}

最小生成树+倍增（100 pts）

#include <bits/stdc++.h>

using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 100010, M = 10 * N;

int n, m;
int h[N], w[N << 1], e[N << 1], ne[N << 1], idx = 1;
int f[N][20], g[N][20], lazy[N][20];
int fa_edge[N], dep[N], in_tree[M], ans[M], edge_id[N << 1];

struct Edge {
	int a, b, c, id;
	Edge() {};
	Edge(int _a, int _b, int _c, int _id): a(_a), b(_b), c(_c), id(_id) {};
	bool operator < (const Edge& x) { return c < x.c; }
} edges[M];

void add(int a, int b, int c) {
	e[ ++ idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx;
}

class DSU {
public:
	int p[N], sz[N];
	DSU() { for (int i = 1; i < N; p[i] = i, sz[i] = 1, i ++ ); }
	int find(int x) {
		if (p[x] != x) p[x] = find(p[x]);
		return p[x];
	}
	void merge(int a, int b) {
		int pa = find(a), pb = find(b);
		if (sz[pa] < sz[pb]) sz[pb] += sz[pa], p[pa] = pb;
		else sz[pa] += sz[pb], p[pb] = pa;
	}
	bool check(int a, int b) { return find(a) == find(b); }
} dsu;

void bfs(int st) {
	queue<int> q;
	q.push(st);
	dep[st] = 1;
	while (q.size()) {
		auto t = q.front(); q.pop();
		for (int i = h[t]; i; i = ne[i]) {
			int j = e[i];
			if (dep[j]) continue;
			dep[j] = dep[t] + 1;
			f[j][0] = t, g[j][0] = w[i];
			fa_edge[j] = edge_id[i];
			for (int k = 1; k <= 18; k ++ ) {
				int fa = f[j][k - 1];
				f[j][k] = f[fa][k - 1];
				g[j][k] = max(g[j][k - 1], g[fa][k - 1]);
			}
			q.push(j);
		}
	}
}

int get_max(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	int d = dep[a] - dep[b], res = 0;
	for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? res = max(res, g[a][i]), a = f[a][i] : 0;
	if (a == b) return res;
	for (int i = 18; i >= 0; i -- ) {
		if (f[a][i] == f[b][i]) continue;
		res = max({res, g[a][i], g[b][i]});
		a = f[a][i], b = f[b][i];
	}
	return max({res, g[a][0], g[b][0]});
}

int lca(int a, int b) {
	if (dep[a] < dep[b]) swap(a, b);
	int d = dep[a] - dep[b];
	for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? a = f[a][i] : 0;
	if (a == b) return a;
	for (int i = 18; i >= 0; i -- ) {
		if (f[a][i] == f[b][i]) continue;
		a = f[a][i], b = f[b][i];
	}
	return f[a][0];
}

void kruskal() {
	sort(edges + 1, edges + m + 1);
	for (int i = 1; i <= m; i ++ ) {
		int a = edges[i].a, b = edges[i].b, c = edges[i].c;
		if (!dsu.check(a, b)) {
			in_tree[i] = true;
			add(a, b, c), add(b, a, c);
			edge_id[idx ^ 1] = edge_id[idx] = edges[i].id;
			dsu.merge(a, b);
		}
	}
}

void modify(int a, int b, int c) {
	if (dep[a] < dep[b]) swap(a, b);
	int d = dep[a] - dep[b], res = 0;
	for (int i = 18; i >= 0; i -- ) (d >> i & 1) ? lazy[a][i] = min(lazy[a][i], c), a = f[a][i] : 0;
	if (a == b) return;
	for (int i = 18; i >= 0; i -- ) {
		if (f[a][i] == f[b][i]) continue;
		lazy[a][i] = min(lazy[a][i], c);
		lazy[b][i] = min(lazy[b][i], c);
		a = f[a][i], b = f[b][i];
	}
	lazy[a][0] = min(lazy[a][0], c);
	lazy[b][0] = min(lazy[b][0], c);
}

void pushdown() {
	for (int k = 18; k; k -- ) {
		for (int i = 1; i <= n; i ++ ) {
			lazy[i][k - 1] = min(lazy[i][k - 1], lazy[i][k]);
			lazy[f[i][k - 1]][k - 1] = min(lazy[f[i][k - 1]][k - 1], lazy[i][k]);
		}
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= m; i ++ ) {
		int a = read(), b = read(), c = read();
		edges[i] = Edge(a, b, c, i);
	}
	kruskal();
	bfs(1);
	for (int i = 1; i <= n; i ++ ) fill(lazy[i], lazy[i] + 18 + 1, 1000000000);
	for (int i = 1; i <= m; i ++ ) {
		if (!in_tree[i]) {
			int a = edges[i].a, b = edges[i].b, c = edges[i].c;
			ans[edges[i].id] = get_max(a, b);
			modify(a, b, c);
		}
	}
	pushdown();
	for (int i = 2; i <= n; i ++ ) ans[fa_edge[i]] = lazy[i][0];
	for (int i = 1; i <= m; i ++ ) printf("%d\n", ans[i]);
	return 0;
}

同学的树剖（100 pts）

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int s = 0, k = 1;
    char c = getchar();
    while (c > '9' || c < '0') {
        if (c == '-') k = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        s = (s << 3) + (s << 1) + (c ^ 48);
        c = getchar();
    }
    return s * k;
}

const int N = 1e5 + 10, M = 1e6 + 10;
int n, fat[N], tim, id[N], a[N], dfn[N], m, head[N], nq, cnt, dis[N][19], fa[N][19], dep[N], top[N], son[N],
    siz[N], ans[M];
bool vks[M];
queue<int>q;
struct edge {
    int u, v, w, id;
} qu[M];
struct EDGE {
    int v, nxt, w;
} e[N << 1];
struct node {
    int tag, v;
} t[N << 2];

void add(int u, int v, int w) {
    e[++cnt].v = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt;
}

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int find(int x) {
    if (fat[x] == x) return x;
    else return fat[x] = find(fat[x]);
}

void kruskal() {
    sort(qu + 1, qu + 1 + m, cmp);
    for (int i = 1; i <= n; i++) fat[i] = i;
    for (int i = 1, x, y; i <= m; i++) {
        x = qu[i].u, y = qu[i].v;
        x = find(x), y = find(y);
        if (x != y) {
            fat[x] = y;
            vks[i] = true;
            add(qu[i].u, qu[i].v, qu[i].w);
            add(qu[i].v, qu[i].u, qu[i].w);
        }
    }
}

void bfs(int s) {
    dep[s] = 1;
    q.push(s);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (dep[v]) continue;
            dep[v] = dep[x] + 1;
            fa[v][0] = x;
            dis[v][0] = e[i].w;
            q.push(v);
            for (int j = 1; j <= nq; j++)
                fa[v][j] = fa[fa[v][j - 1]][j - 1],
                           dis[v][j] = max(dis[v][j - 1], dis[fa[v][j - 1]][j - 1]);
        }
    }
}

void dfs1(int x, int fa) {
    siz[x] = 1;
    for (int i = head[x]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa) continue;
        dfs1(v, x);
        siz[x] += siz[v];
        if (siz[v] > siz[son[x]]) son[x] = v;
    }
}

void dfs2(int x, int t) {
    top[x] = t;
    dfn[x] = ++tim;
    id[tim] = x;
    if (son[x]) dfs2(son[x], t);
    for (int i = head[x]; i; i = e[i].nxt) {
        int v = e[i].v;
        if (v != fa[x][0] && v != son[x]) dfs2(v, v);
    }
}

void build(int s, int l, int r) {
    t[s].v = 1e9;
    t[s].tag = 1e9;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(s << 1, l, mid);
    build(s << 1 | 1, mid + 1, r);
}

int qdis(int x, int y) {
    int t = 0;
    if (dep[x] > dep[y]) swap(x, y);
    for (int i = nq; i >= 0; i--)
        if (dep[fa[y][i]] >= dep[x])
            t = max(t, dis[y][i]), y = fa[y][i];
    if (x == y) return t;
    for (int i = nq; i >= 0; i--)
        if (fa[x][i] != fa[y][i])
            t = max({t, dis[x][i], dis[y][i]}), x = fa[x][i], y = fa[y][i];
    return max({t, dis[x][0], dis[y][0]});
}

void pushdown(int s) {
    t[s << 1].v = min(t[s << 1].v, t[s].tag);
    t[s << 1 | 1].v = min(t[s << 1 | 1].v, t[s].tag);
    t[s << 1].tag = min(t[s << 1].tag, t[s].tag);
    t[s << 1 | 1].tag = min(t[s << 1 | 1].tag, t[s].tag);
    t[s].tag = 1e9;
}

void update(int s, int l, int r, int L, int R, int v) {
    if (L > R) return;
    if (L <= l && r <= R) {
        t[s].v = min(t[s].v, v);
        t[s].tag = min(t[s].tag, v);
        return;
    }
    pushdown(s);
    int mid = (l + r) >> 1;
    if (L <= mid) update(s << 1, l, mid, L, R, v);
    if (R > mid) update(s << 1 | 1, mid + 1, r, L, R, v);
}

void getans(int s, int l, int r) {
    if (l == r) {
        a[id[l]] = t[s].v;
        return;
    }
    pushdown(s);
    int mid = (l + r) >> 1;
    getans(s << 1, l, mid);
    getans(s << 1 | 1, mid + 1, r);
}

void upd(int x, int y, int w) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, 1, tim, dfn[top[x]], dfn[x], w);
        x = fa[top[x]][0];
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, 1, tim, dfn[x] + 1, dfn[y], w);
}

int main() {
    n = read();
    m = read();
    nq = log2(n);

    for (int i = 1, u, v, w; i <= m; i++) {
        u = read(), v = read();
        w = read();
        qu[i] = {u, v, w, i};
    }

    kruskal();
    bfs(1);
    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, tim);

    for (int i = 1; i <= m; i++) {
        if (!vks[i]) {
            upd(qu[i].u, qu[i].v, qu[i].w);
            ans[qu[i].id] = qdis(qu[i].u, qu[i].v);
        }
    }

    getans(1, 1, tim);

    for (int i = 1; i <= m; i++) {
        if (vks[i]) {
            if (dfn[qu[i].u] > dfn[qu[i].v]) swap(qu[i].u, qu[i].v);
            ans[qu[i].id] = a[qu[i].v];
        }
    }

    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);

    return 0;
}