记录编号	454095	评测结果	AAAAAAAAAA
题目名称	[Codeforces 828F] 最好的边权	最终得分	100
用户昵称	胡嘉兴	是否通过	通过
代码语言	C++	运行时间	0.297 s
提交时间	2017-09-28 11:31:12	内存使用	39.99 MiB

#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>

#define N 200000 + 7
#define INF 0x3f3f3f3f

using namespace std;

int n, m, r[N], istree[N] = {0}, p[N], deep[N] = {0}, ans[N], f[N][20], max_w[N][20];

typedef struct edge
{
	int u;
	int v;
	int w;
	int num;
}ED;

ED e[N];

vector<ED> G[N];

int max(int a, int b)
{
	return a > b ? a : b;
}
int min(int a, int b)
{
	return a < b ? a : b;
}
int cmp(ED a, ED b)
{
	return a.w < b.w;
}
int find(int x)
{
	return x == p[x] ? x : p[x] = find(p[x]);
}
void Kruskal()
{
	int i;
	for(i = 1; i <= n; i++)
	{
		p[i] = i;
	}
	sort(e + 1, e + m + 1, cmp);
	for(i = 1; i <= m; i++)
	{
		int x = e[i].u, y = e[i].v;
		int fx = find(x), fy = find(y);
		if(fx != fy)
		{
			p[fy] = fx;
			istree[e[i].num] = 1;
			G[x].push_back(e[i]);
			swap(e[i].u, e[i].v);
			G[y].push_back(e[i]);
		}
	}
	return;
}
void dfs(int now, int fa, int d)
{
	int i;
	deep[now] = deep[fa] + 1;
	f[now][0] = fa;
	max_w[now][0] = d;
	for(i = 1; i <= 18; i++)
	{
		f[now][i] = f[f[now][i - 1]][i - 1];
		max_w[now][i] = max(max_w[now][i - 1], max_w[f[now][i - 1]][i - 1]);
	}
	for(i = 0; i < G[now].size(); i++)
	{
		ED t = G[now][i];
		int v = t.v;
		if(v == fa)
		{
			continue;
		}
		r[v] = t.num;
		dfs(v, now, t.w);
	}
	return;
}
int lca(int a,int b, int &d)
{
	int i;
	if(deep[a] > deep[b])
	{
		swap(a, b);
	}
	for(i = 18; i >= 0; i--)
	{
		if(deep[f[b][i]] >= deep[a])
		{
			d = max(d, max_w[b][i]);
			b = f[b][i];
		}
	}
	if(a == b)
	{
		return a;
	}
	for(i = 18; i >= 0; i--)
	{
		if(f[a][i] != f[b][i])
		{
			d = max(max(max_w[a][i], max_w[b][i]), d);
			a = f[a][i];
			b = f[b][i];
		}
	}
	d = max(max(max_w[a][0], max_w[b][0]), d);
	return f[a][0];
}
void slove(int x, int u, int d)
{
	x = find(x);
	while(deep[u] < deep[x])
	{
		ans[r[x]] = min(ans[r[x]], d);
        int y = find(f[x][0]);
		p[x] = y;
	    x = find(x);
	}
	return;
}
int main()
{
	int i, j;
	freopen("BEW.in", "r", stdin);
	freopen("BEW.out", "w", stdout);

	scanf("%d%d", &n, &m);

	for(i = 1; i <= m; i++)
	{

		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

		e[i].num = i;
	}
	Kruskal();
	dfs(1, 0, 0);
	memset(ans, INF, sizeof(ans));
	for(i = 1; i <= n; i++)
	{
		p[i] = i;
	}
	for(i = 1; i <= m; i++)
	{
		if(!istree[e[i].num])
		{
			ans[e[i].num] = 0;
			int x = lca(e[i].u, e[i].v, ans[e[i].num]);
			ans[e[i].num]--;
		 	slove(e[i].u, x, e[i].w - 1);
			slove(e[i].v, x, e[i].w - 1);
		}
	}
	for(i = 1; i <= m; i++)
	{

		printf("%d ", ans[i] == INF ? -1 : ans[i]);

	}
	cout << endl;
	return 0;
}