Geiz-Revive > CF827D-BestEdgeWeight

CF827D-BestEdgeWeight

2019-06-20

LCT

$\Large\color{orange}{Describe}$

题意是要求出一条边的边权为多大时，能出现在所有的最小生成树中，因此我们先随便造一棵最小生成树，进行分类讨论。

  • 对于非树边，它的答案是它链接的这两个点在最小生成树上的链的最大值再-1，这样它才能替换掉树边。
  • 对于树边，它的答案是能够让它所链接的两个点联通的非树边的最小值再减一，否则它会被替换掉。

之后可以发现，我们需要的只不过是一个能查询链上最大值、链上取最小值的一个数据结构，因此树剖$\Theta(nlog^2_n)$，LCT $\Theta(nlog_n)$

$\large Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#pragma region revive
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define inl inline
#define re register int
#define fa(x) t[x].fa
#define son(x,y) t[x].child[y]
#define ls(x) t[x].child[0]
#define rs(x) t[x].child[1]
#define ll long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
using namespace std;
#ifndef _DEBUG
#define getchar() (*(IOB.in.p++))
#define putchar(c) (*(IOB.out.p++)=(c))
#define io_eof() (IOB.in.p>=IOB.in.pend)
struct IOBUF { struct { char buff[1 << 26], *p, *pend; }in; struct { char buff[1 << 26], *p; }out; IOBUF() { in.p = in.buff; out.p = out.buff; in.pend = in.buff + fread(in.buff, 1, 1 << 26, stdin); }~IOBUF() { fwrite(out.buff, 1, out.p - out.buff, stdout); } }IOB;
#endif
template<typename IO>
inl void write(IO x) {
	if (x == 0) return (void)putchar('0');
	if (x < 0)putchar('-'), x = -x;
	static char buf[30];
	char* p = buf;
	while (x) {
		*(p++) = x % 10 + '0';
		x /= 10;
	}
	while (p > buf)putchar(*(--p));
}
inl void writestr(const char *s) { while (*s != 0)putchar(*(s++)); }
template<typename IO>inl void writeln(IO x) { write(x), putchar('\n'); }
template<typename IO>inl void writesp(IO x) { write(x), putchar(' '); }
inl int readstr(char *s) {
	char *begin = s, c = getchar();
	while (c < 33 || c>127) {
		c = getchar();
	}
	while (c >= 33 && c <= 127) {
		*(s++) = c;
		c = getchar();
	}
	*s = 0;
	return s - begin;
}
template<typename IO>
inl IO read() {
	IO x = 0;
	register bool w = 0;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return w ? -x : x;
}
#pragma endregion
int fa[1000001], ans[1000001];
bool vis[1000001];
struct node {
	int child[2], fa, w, max, tag;
	bool filp;
}t[1000001];
inl void maintain(int x) {
	t[x].max = max({ t[ls(x)].max, t[rs(x)].max, t[x].w });
}
inl bool poi(int x) { return rs(fa(x)) == x; }
inl bool nroot(int x) { return ls(fa(x)) == x || rs(fa(x)) == x; }
inl void reverse(int x) { swap(ls(x), rs(x)), t[x].filp ^= 1; }
inl void change(int x, int w) { ans[x] = min(ans[x], w), t[x].tag = min(t[x].tag, w); }
inl void rotate(int x) {
	re f = fa(x), gf = fa(f), fs = poi(x), gfs = poi(f), s = t[x].child[fs ^ 1];
	if (nroot(f))t[gf].child[gfs] = x;
	t[x].child[fs ^ 1] = f, t[f].child[fs] = s;
	if (s)fa(s) = f;
	fa(f) = x, fa(x) = gf, maintain(f);
}
inl void pushdown(int x) {
	if (t[x].filp) {
		if (ls(x))reverse(ls(x));
		if (rs(x))reverse(rs(x));
		t[x].filp = 0;
	}
	if (t[x].tag != inf) {
		if (ls(x))change(ls(x), t[x].tag);
		if (rs(x))change(rs(x), t[x].tag);
		t[x].tag = inf;
	}
}
inl void push(int x) {
	if (nroot(x))push(fa(x));
	pushdown(x);
}
inl void splay(int x) {
	push(x);
	while (nroot(x)) {
		if (nroot(fa(x)))poi(x) == poi(fa(x)) ? rotate(fa(x)) : rotate(x);
		rotate(x);
	}
	maintain(x);
}
inl void access(int x) {
	for (re i = 0; x; x = fa(i = x)) splay(x), rs(x) = i, maintain(x);
}
inl void makeroot(int x) {
	access(x), splay(x), reverse(x);
}
inl void split(int x, int y) {
	makeroot(y), access(x), splay(x);
}
inl void link(int x, int y) {
	split(x, y), fa(y) = x;
}
struct edge {
	int u, v, w, id;
	bool operator <(const edge &fff)const {
		return w < fff.w;
	}
}e[1000001];
inl int find(int x) { return fa[x] ? fa[x] = find(fa[x]) : x; }
signed main() {
	re n = read<int>(), m = read<int>(), u, v, w = n + m, now;
	for (re i = 1; i <= w; i++)t[i].tag = ans[i] = inf;
	for (re i = 1; i <= m; i++) u = read<int>(), v = read<int>(), w = read<int>(), e[i] = edge{ u,v,w }, e[i].id = i;
	sort(e + 1, e + 1 + m);
	for (re i = 1; i <= m; i++) {
		u = e[i].u, v = e[i].v, w = e[i].w, now = e[i].id + n;
		if (find(u) != find(v)) {
			fa[find(v)] = u;
			t[now].w = t[now].max = w;
			link(u, now), link(v, now), vis[now] = 1;
		}
		else {
			split(u, v);
			ans[now] = t[u].max - 1;
			change(u, w);
		}
	}
	for (re i = n + 1, k = n + m; i <= k; i++) {
		if (vis[i]) {
			access(i), splay(i), writesp(ans[i] == inf ? -1 : ans[i] - 1);
		}
		else {
			writesp(ans[i]);
		}
	}
}