今天是几场下来第一次完整搞出一道题

虽然跑的贼慢，方法不够优，比 $\text{std}$ 慢 $200ms$。。

$\text{score：0 + 100 + 0 = 100 rk：16/32}$

Problem A：Geometric Progressions

题目描述

首项为 $a$ 且公比为 $b$ 的等比数列是一个形如 $a, ab, ab^2, ab^3, …$ 的数字序列

你被给定了 $n$ 个整数等比数列。你的任务是找出最小的整数 $x$，使得它是所有给定的序列的元素，或者声明这样的整数不存在

数据范围

对 $100\%$ 的数据，$1 \le n \le 100, ~ 1 \le a, b \le 10^9$

题解

原题 CF571E

首先将所有 $a, b$ 分解质因数，得到大小为 $m$ 质因数集 $\{p_1, p_2, …, p_m\}$

设 $c_{i, j}$ 表示 $a_i$ 分解质因数后 $p_j$ 的幂次，$d_{i, j}$ 表示 $b_i$ 分解质因数后 $p_j$ 的幂次，那么答案即可被表示为 $\prod\limits_{i = 1}^m p_i^{c_{1, i} + k \times d_{1, i}}$，其中 $k \in N$

考虑每次将两对 $a, b$ 合并，设之前合并得到的 $a, b$ 分解质因数后的质因数幂次数组 $A, B$，其中 $A_i$ 表示第 $i$ 个质因数的幂次，再设准备与之合并的 $a, b$ 的质因数幂次数组 $C, D$

那么现在分为仅有一解、有无数解、无解三种情况

对 $A, B$ 单独考虑，设答案 $p_i$ 幂次 $t_i$，则有
$$
\left\{
\begin{aligned}
t_i &= A_i + k \times B_i \\
t_j &= A_j + k \times B_j
\end{aligned}
\right. \\
\Rightarrow
t_i = A_i + \frac{B_i}{B_j}(t_j - A_j)
$$
也就是说 $t_j$ 和 $t_i$ 的关系是一条斜率为 $\frac{B_i}{B_j}$ 的直线

同理对 $C, D$，有 $t_i = C_i + \frac{D_i}{D_j}(t_j - C_j)$

那么仅有一解的条件即为它们之间有交点，即 $\frac{B_i}{B_j} = \frac{D_i}{D_j}$，这种情况直接解出来就好了

那么考虑剩下的情况，$t_i = A_i + k_1 \times B_i = C_i + k_2 \times D_i$ 可以转化成 $k_2 \times D_i - k_1 \times B_i = A_i - C_i$，然后用 $ExGCD$ 求解，注意由于它们 $k_1, k_2$ 都相同，所以要满足每组方程是否满足比例关系，不满足则无解，其实我觉得上面那个 $\frac{B_i}{B_j} \ne \frac{D_i}{D_j}$ 则只有一解也应该可以用这个来理解，然后就相当于解一个二元一次方程

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 100 + 10;
const int MAXM = 900 + 10;

inline LL power (LL x, LL p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

int N;
const int M = 1e04;
int oa[MAXN], ob[MAXN];

LL GCD (LL a, LL b) { return ! b ? a : GCD (b, a % b); }
void exGCD (LL a, LL b, LL& x, LL& y) {
	if (! b) { x = 1, y = 0; return ; }
	exGCD (b, a % b, y, x);
	y -= a / b * x;
}

int prime[MAXM]= {0}, pn = 0;
void separ (int x) {
	for (int i = 2; i * i <= x; i ++)
		if (! (x % i)) {
			prime[++ pn] = i;
			while (! (x % i)) x /= i;
		}
	if (x > 1) prime[++ pn] = x;
}
int pcnt[2][MAXN][MAXM]= {0};
void cencus (int p, int id, int x) {
	for (int i = 1; i <= pn; i ++)
		if (! (x % prime[i])) {
			while (! (x % prime[i])) {
				x /= prime[i];
				pcnt[p][id][i] ++;
			}
		}
}

LL a[MAXM], b[MAXM], c[MAXM], d[MAXM];
bool merge () {
	LL sb = 0, sd = 0;
	for (int i = 1; i <= pn; i ++) { sb += b[i]; sd += d[i]; }
	if (! sb && ! sd) {
		for (int i = 1; i <= pn; i ++)
			if (a[i] != c[i])
				return false;
		return true;
	}
	if (! sb || ! sd) {
		if (! sd) { swap (sb, sd); swap (a, c); swap (b, d); }
		LL k = - 1;
		for (int i = 1; i <= pn; i ++)
			if (d[i]) {
				if (c[i] > a[i] || (a[i] - c[i]) % d[i]) return false;
				LL pk = (a[i] - c[i]) / d[i];
				if (k != - 1 && pk != k) return false;
				k = pk;
			}
		return true;
	}
	{
		int i, j;
		for (i = 1; i <= pn; i ++)
			if (sb * d[i] != sd * b[i])
				break;
		if (i <= pn) {
			for (j = 1; j <= pn; j ++)
				if (b[i] * d[j] != d[i] * b[j]) // 只有一个解
					break;
			LL ka = d[j] * (c[i] - a[i]) - d[i] * (c[j] - a[j]);
			LL kb = b[j] * (c[i] - a[i]) - b[i] * (c[j] - a[j]);
			LL down = d[j] * b[i] - d[i] * b[j];
			if (down < 0) ka = - ka, kb = - kb, down = - down;
			if (ka < 0 || kb < 0 || ka % down || kb % down) return false;
			ka /= down, kb /= down;
			for (int k = 1; k <= pn; k ++) {
				if (a[k] + ka * b[k] != c[k] + kb * d[k]) return false;
				a[k] = a[k] + ka * b[k], b[k] = 0;
			}
			return true;
		}
	}
	// ExGCD合并
	LL rb = 0, rd = 0, r = 0;
	for (int i = 1; i <= pn; i ++)
		if (b[i]) {
			LL g = GCD (b[i], d[i]);
			rb = b[i] / g, rd = d[i] / g;
			if ((a[i] - c[i]) % g) return false;
			r = (a[i] - c[i]) / g;
			break;
		}
	for (int i = 1; i <= pn; i ++)
		if (r * (b[i] / rb) != a[i] - c[i]) // 判断是否成比例
			return false;
		if (r < 0) swap (a, c), swap (b, d), swap (rb, rd), r = - r;
	LL ka, kb;
	exGCD (rb, rd, ka, kb);
	ka = (ka * (- r) % rd + rd) % rd;
	for (int i = 1; i <= pn; i ++)
		a[i] += ka * b[i], b[i] *= rd;
	return true;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum ();
	for (int i = 1; i <= N; i ++) oa[i] = getnum (), ob[i] = getnum ();
	for (int i = 1; i <= N; i ++) separ (oa[i]), separ (ob[i]);
	sort (prime + 1, prime + pn + 1);
	pn = unique (prime + 1, prime + pn + 1) - prime - 1;
	for (int i = 1; i <= N; i ++) cencus (0, i, oa[i]), cencus (1, i, ob[i]);
	for (int i = 1; i <= pn; i ++) a[i] = pcnt[0][1][i], b[i] = pcnt[1][1][i];
	for (int i = 2; i <= N; i ++) {
		for (int j = 1; j <= pn; j ++) c[j] = pcnt[0][i][j], d[j] = pcnt[1][i][j];
		if (! merge ()) { puts ("-1"); return 0; }
	}
	LL ans = 1;
	for (int i = 1; i <= pn; i ++) ans = ans * power (prime[i], a[i]) % MOD;
	cout << ans << endl;

	return 0;
}

Problem B：Bichrome Spanning Tree

题目描述

我们有一个 $n$ 个点 $m$ 条边的带权无向图。图中的第 $i$ 条边连接了节点 $u_i, v_i,$，权重为 $w_i$。另外，你还被给定了一个整数 $X$。

请求出将每条边染成黑色或白色，且满足下面的条件的方案数模 $10^9 + 7$ 的值

  • 图中存在一棵同时包含染成白色的边和染成黑色的边的生成树。另外，在所有这种生成树中，权重最小的一棵的权重恰为 $X$

这里，一棵生成树的权重定义为生成树中边的权重的和

数据范围

对 $100\%$ 的数据，$1 \le n \le 1000, ~ 1 \le m \le 2000, ~ 1 \le w_i \le 10^9, ~ 1 \le X \le 10^{12}$

给出的数据保证图联通，不存在重边，不存在自环

题解

原题 ARC093C

方法一

先讲讲我的方法吧

显然对一棵权重 $< X$ 的树，它所有的边的颜色都应该相同，那么我们考虑对每条边判断它会不会有这种限制

此时直接用 $Kruskal$ 求出包含该边的最小生成树，若其权重 $< X$，则该边的染色就会被限制，称一类边；若其权重 $> X$，则它属于染色情况不论如何都不会对答案造成贡献的边，称二类边；若其权重 $= X$，则需要着重考虑，称三类边

这里考虑两棵在相同的图上但边集完全无交集的最小生成树，它们一定可以构成一个新的最小生成树，该最小生成树的边集与原两棵树的边集分别有交，这个也很好证明，因为最小生成树一定是最小瓶颈生成树，即最大边最小，那么它们之间一定可以互相替换，从而构成一棵新的 $MST$，至于对那些权重 $< X$ 的树，也拥有类似该定理，证明类比一下就好了

自此我们就可以认为所有二类边的颜色一定是相同的

设某条三类边 $E$，三类边的总数为 $m$

现在只需枚举 $E$ 来进行组合计数，强制令 $E$ 染色与一类边不同，则剩余 $m - 1$ 条边则可随意染色，为避免算重，枚举 $m - 1$ 条边中与 $E$ 染色相同的个数 $j$，则 $E$ 在枚举到 $j$ 加上的贡献即为 $\frac{C (m - 1, j)}{j + 1}$，记得最后乘二，但对不存在一类边的情况要特判一下

那么最后再设三类边个数 $ext$，将之前统计得到的答案乘上 $2^{ext}$ 即可

时间复杂度 $O \big(nm \times \alpha(n)\big)$

代码（方法一）

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXN = 1000 + 10;
const int MAXM = 2000 + 10;

inline LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}
LL pow2[MAXM]= {0};

struct LFS { int to, w, next; };
LFS Link[MAXM << 1];
int Head[MAXN]= {0}, sze = 0;
void Insert (int u, int v, int w) {
	Link[++ sze].to = v;
	Link[sze].w = w;
	Link[sze].next = Head[u];

	Head[u] = sze;
}

LL fact[MAXM]= {0}, invfact[MAXM]= {0};
LL inv[MAXM]= {0};
inline LL C (int n, int m) { return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD; }

int N, M;
LL X;
struct Edge {
	int u, v, w;
	Edge (int u = 0, int v = 0, int w = 0) : u (u), v (v), w (w) {}
	bool operator < (const Edge& p) const { return w < p.w; }
} ;
Edge edge[MAXM];

int fa[MAXN]= {0};
int find (int x) { return fa[x] == x ? x : fa[x] = find (fa[x]); }
LL Kruskal () {
	LL ret = 0;
	for (int i = 1; i <= M; i ++) {
		int x = edge[i].u, y = edge[i].v, w = edge[i].w;
		int fx = find (x), fy = find (y);
		if (fx == fy) continue;
		fa[fx] = fy; ret += w;
		Insert (x, y, w), Insert (y, x, w);
	}
	return ret;
}
int white[MAXM]= {0}, black[MAXM]= {0};
int wn = 0, bn = 0;
LL cencus () {
	LL ret = 0;
	for (int q = 1; q <= bn; q ++) {
		int i = black[q];
		for (int j = 1; j <= N; j ++) { fa[j] = j; Head[j] = 0; }
		sze = 0;
		int u = edge[i].u, v = edge[i].v, w = edge[i].w;
		fa[u] = v;
		Insert (u, v, w), Insert (v, u, w);
		Kruskal ();
		LL add = 0;
		for (int j = 0; j <= bn - 1 - (! wn); j ++)
			add = (add + C (bn - 1, j) * inv[j + 1] % MOD) % MOD;
		ret = (ret + add) % MOD;
	}
	if (wn) ret = 2ll * ret % MOD;
	return ret;
}
LL solve () {
	LL ans = 0; int ext = 0;
	for (int i = 1; i <= M; i ++) {
		if (1ll * edge[i].w > X) { ext ++; continue; }
		for (int j = 1; j <= N; j ++) { fa[j] = j; Head[j] = 0; }
		sze = 0;
		int u = edge[i].u, v = edge[i].v, w = edge[i].w;
		fa[u] = v;
		LL x = w + Kruskal ();
		if (x < X) white[++ wn] = i;
		else if (x == X) black[++ bn] = i;
		else ext ++;
	}
	ans = cencus ();
	ans = ans * pow2[ext] % MOD;
	return ans;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum (); cin >> X;
	if (N == 1) { puts ("0"); return 0; }
	pow2[0] = 1;
	for (int i = 1; i <= max (N, M); i ++) pow2[i] = pow2[i - 1] * 2ll % MOD;
	fact[0] = invfact[0] = 1;
	inv[1] = fact[1] = invfact[1] = 1;
	for (int i = 2; i <= M; i ++) {
		inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
		fact[i] = fact[i - 1] * i % MOD;
		invfact[i] = invfact[i - 1] * inv[i] % MOD;
	}
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum (), w = getnum ();
		edge[i] = Edge (u, v, w);
	}
	sort (edge + 1, edge + M + 1);
	cout << solve () << endl;
	
	return 0;
}

方法二

题解的方法，我觉着挺妙

先随便取一个 $MST$ 设为 $T$，设其权重和 $w(T)$，显然只需考虑 $w(T) \le X$

对 $w(T) = X$，可以先加上让其内部不全部染相同色，剩余边随意染色，即贡献 $(2^{n - 1} - 2) \cdot 2^{m - n + 1}$

接下来考虑 $T$ 染色全部相同的情况，不妨设 $T$ 中边均为黑边

每次替换一个不在 $T$ 中的白边到 $T$，则最多替换一次

证明反向思考一下就行了，每次替换权重一定不会减少，那么假定现在替换了两个白边，但全图的黑白边 $MST$ 仍不包括你第二次替换的边，因为第二次替换出来的黑边此时就满足条件了

对每次替换，若替换第 $i$ 条边，则会增大 $cost(i) = w_i - \max\{w_j | (u_j, v_j) 在T中(u_i, v_i)两点间路径上\}$（题解表述）的贡献，因此一定选最小边替换

求 $cost(i)$ 跳个倍增就好了

那么最后将所有 $i$ 的 $cost(i)$ 排个序，设排序后某条边排在位置 $p$，则其对答案贡献 $2^{n + m - 1 - p}$（只有后面的边才能任意染色）

时间复杂度 $O (m \log n)$

Problem C：Network

题面

题解

先计算在不反转用户的情况下，所有用户的 $MS(u)$

考虑点分治，现在递归到分治中心 $p$，设 $p$ 子树点 $x$ 到 $p$ 的边的最小值和最大值 $(mi_x, ma_x)$，假设现在有服务器 $i$，用户 $j$，都是 $p$ 的子树结点，计算 $MS(j)$，考虑有哪几种情况会贡献到 $MS(j)$，即是 $ma_i - mi_x$、$ma_i - mi_j$、$ma_j - mi_i$，同时 $(mi_i, ma_i), (mi_j, ma_j)$ 之间不存在任何关系，那么也就是说只需求得 $p$ 子树中满足 $ma_i - mi_i$ 最大，或 $ma_i$ 最大、或 $mi_i$ 最大，即可更新其它所有的用户（当然要与 $i$ 不同子树），又考虑到同子树不能互相更新，所以还得记录上面三者的次大值，这样就可以求出所有 $MS(u)$

接下来计算反转用户的情况，最小值最大，考虑二分答案

设此时二分答案 $mid$，继续考虑点分治（实际上只需要看点分树就好了），设分治中心 $p$，设在两个子树的用户 $i, j$，若使 $check$ 失败则需要找到一对 $i, j$，反转 $i$，使得 $Waste (j, i) < mid$

将 $p$ 所有储存下来的 $(mi_x, ma_x)$ 按 $mi_x$ 排序，则对 $mi_j \le mi_x$，欲使其失败则需满足 $ma_i - mi_j < mid$，即 $ma_x < mi_j + mid$，对 $mi_j > mi_x$，欲使其失败则需满足 $mi_i > \max(ma_i, ma_j) - mid$，当然已经排除了所有满足 $ma_x - mi_x \ge mid$（对第一种情况）或 $MS(x) \ge mid$（对两种情况）的点，然后和前面相同可以线性处理

时间复杂度 $O (n \log n \log V)$

代码

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;

const int INF = 0x7fffffff;

struct LFS { int to, w, next; } ;
LFS Link[MAXM << 1];
int Head[MAXN]= {0}, size = 0;
void Insert (int u, int v, int w) {
	Link[++ size].to = v;
	Link[size].w = w;
	Link[size].next = Head[u];

	Head[u] = size;
}

int N;
int type[MAXN]= {0};

int subsize[MAXN]= {0};
bool visit[MAXN]= {false};
int rt, minval = INF, fa;
void grvy (int n, int root, int father) {
	subsize[root] = 1;
	int maxpart = 0;
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (v == father || visit[v]) continue;
		grvy (n, v, root);
		subsize[root] += subsize[v];
		maxpart = max (maxpart, subsize[v]);
	}
	maxpart = max (maxpart, n - subsize[root]);
	if (maxpart < minval) { rt = root; fa = father; minval = maxpart; }
}
struct node {
	int l, r, id, bel;
	// min value, max value, original index, 子树从属
	node (int l = 0, int r = 0, int id = 0, int bel = 0) : l (l), r (r), id (id), bel (bel) {}
	bool operator < (const node& p) const {
		if (l == p.l) return r < p.r;
		return l < p.l;
	}
} ;
vector<node> a[MAXN];
int minv[MAXN], maxv[MAXN];
void DFS (int root, int father, int bel) {
	a[rt].push_back(node (minv[root], maxv[root], root, bel));
	for (int i = Head[root]; i; i = Link[i].next) {
		int v = Link[i].to, w = Link[i].w;
		if (v == father || visit[v]) continue;
		minv[v] = min (minv[root], w);
		maxv[v] = max (maxv[root], w);
		DFS (v, root, bel);
	}
}
int MS[MAXN]= {0};
void work () {
	minv[rt] = INF, maxv[rt] = 0;
	a[rt].push_back(node (minv[rt], maxv[rt], rt, rt));
	for (int i = Head[rt]; i; i = Link[i].next) {
		int v = Link[i].to, w = Link[i].w;
		if (visit[v]) continue;
		minv[v] = min (minv[rt], w);
		maxv[v] = max (maxv[rt], w);
		DFS (v, rt, v);
	}
	sort (a[rt].begin(), a[rt].end());
	pair<int, int>  fir (- INF, 0), sec (- INF, 0);
	for (int i = 0; i < (int) a[rt].size(); i ++) {
		node x = a[rt][i];
		if (type[x.id]) {
			int ms = x.r - x.l;
			if (ms >= fir.first) {
				if (x.bel != fir.second) sec = fir;
				fir = make_pair (ms, x.bel);
			}
			else if (ms > sec.first && x.bel != fir.second) sec = make_pair (ms, x.bel);
		}
	}
	for (int i = 0; i < (int) a[rt].size(); i ++) {
		node x = a[rt][i];
		if (! type[x.id]) {
			pair<int, int> now = x.bel == fir.second ? sec : fir;
			if (now.second) {
				MS[x.id] = max (MS[x.id], x.r - x.l);
				MS[x.id] = max (MS[x.id], now.first);
			}
		}
	}
	fir = make_pair (- INF, 0), sec = make_pair (- INF, 0);
	for (int i = 0; i < (int) a[rt].size(); i ++) {
		node x = a[rt][i];
		if (type[x.id]) {
			if (x.r >= fir.first) {
				if (x.bel != fir.second) sec = fir;
				fir = make_pair (x.r, x.bel);
			}
			else if (x.r > sec.first && x.bel != fir.second) sec = make_pair (x.r, x.bel);
		}
	}
	for (int i = 0; i < (int) a[rt].size(); i ++) {
		node x = a[rt][i];
		if (! type[x.id]) {
			pair<int, int> now = x.bel == fir.second? sec : fir;
			int r = max (x.r, now.first);
			if (now.second) MS[x.id] = max (MS[x.id], r - x.l);
		}
	}
	fir = make_pair (INF, 0), sec = make_pair (INF, 0);
	for (int i = 0; i < (int) a[rt].size(); i ++) {
		node x = a[rt][i];
		if (type[x.id]) {
			if (x.l <= fir.first) {
				if (x.bel != fir.second) sec = fir;
				fir = make_pair (x.l, x.bel);
			}
			else if (x.l < sec.first && x.bel != fir.second) sec = make_pair (x.l, x.bel);
		}
	}
	for (int i = 0; i < (int) a[rt].size(); i ++) {
		node x = a[rt][i];
		if (! type[x.id]) {
			pair<int, int> now = x.bel == fir.second? sec : fir;
			int l = min (x.l, now.first);
			if (now.second) MS[x.id] = max (MS[x.id], x.r - l);
		}
	}
}
void divide (int n, int x) {
	minval = INF; grvy (n, x, 0);
	visit[rt] = true;
	work ();
	grvy (n, rt, 0);
	for (int i = Head[rt]; i; i = Link[i].next) {
		int v = Link[i].to;
		if (visit[v]) continue;
		divide (subsize[v], v);
	}
}
bool fail[MAXN]= {false};
void doit (int u, int mid) {
	pair<int, int> fir (- INF, 0), sec (- INF, 0);
	for (int i = 0; i < (int) a[u].size(); i ++) {
		node x = a[u][i];
		if (! type[x.id]) {
			pair<int, int> now = x.bel == fir.second ? sec : fir;
			if (now.second && x.r < now.first) fail[x.id] = true;
			if (MS[x.id] >= mid || x.r - x.l >= mid) continue;
			if (x.l + mid >= fir.first) {
				if (x.bel != fir.second) sec = fir;
				fir = make_pair (x.l + mid, x.bel);
			}
			else if (x.l + mid > sec.first && x.bel != fir.second) sec = make_pair (x.l + mid, x.bel);
		}
	}
	fir = make_pair (INF, 0), sec = make_pair (INF, 0);
	for (int i = a[u].size() - 1; i >= 0; i --) {
		node x = a[u][i];
		if (! type[x.id]) {
			pair<int, int> now = x.bel == fir.second ? sec : fir;
			if (now.second && x.l > max (x.r, now.first) - mid) fail[x.id] = true;
			if (MS[x.id] >= mid) continue;
			if (x.r <= fir.first) {
				if (x.bel != fir.second) sec = fir;
				fir = make_pair (x.r, x.bel);
			}
			else if(x.r < sec.first && x.bel != fir.second) sec = make_pair (x.r, x.bel);
		}
	}
}
bool check (int mid) {
	for (int i = 1; i <= N; i ++) fail[i] = type[i];
	for (int i = 1; i <= N; i ++) doit (i, mid);
	for (int i = 1; i <= N; i ++)
		if (! fail[i])
			return true;
	return false;
}

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum ();
	for (int i = 1; i <= N; i ++) type[i] = getnum ();
	int sum = 0;
	for (int i = 1; i <= N; i ++) sum += type[i];
	if (sum >= N - 1) {
		if (sum == N) { puts ("0"); return 0; }
		for (int i = 1; i <= N; i ++)
			if (! type[i]) {
				printf ("%d 0\n", i);
				return 0;
			}
	}
	int maxi = 0, mini = INF;
	for (int i = 1; i < N; i ++) {
		int u = getnum (), v = getnum (), w = getnum ();
		Insert (u, v, w), Insert (v, u, w);
		maxi = max (maxi, w); mini = min (mini, w);
	}
	divide (N, 1);
	int left = 0, right = maxi - mini, ans;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (check (mid)) { ans = mid; left = mid + 1; }
		else right = mid - 1;
	}
	check (ans);
	for (int i = 1; i <= N; i ++)
		if (! fail[i]) {
			printf ("%d %d\n", i, ans);
			break;
		}

	return 0;
}