T1 旅途计费（rail）

简要题意

给出由 $N$ 个站点构成的链、按顺序访问的 $M$ 个站点，以及每条边的直接价格 $A_i$、持卡价格 $B_i<A_i$ 和一次性购卡费 $C_i$。优惠卡互不通用，求完成全部行程的最小总费用。每组 $N,M\le10^5$，各项费用不超过 $10^5$；至多 $10$ 组，同文件 $\sum N,\sum M\le2\times10^5$。

一句话题解

用差分统计每段铁路的使用次数 $x_i$，然后逐段取 $\min(x_iA_i,C_i+x_iB_i)$，最后求和。

完整题解

从单次行程获得20分

测试点 $1\sim4$ 中 $M=2$，只有一次从 $P_1$ 前往 $P_2$ 的行程。令 $l=\min(P_1,P_2)$、$r=\max(P_1,P_2)$，经过的铁路编号恰好是 $l,l+1,\ldots,r-1$。每段只经过一次，费用取 $\min(A_i,B_i+C_i)$ 即可，时间 $O(N+M)$、空间 $O(N+M)$。

下面的实现将这个单次费用按经过次数累加，能完整解决该档；在一般数据中，它相当于每次经过时重新购卡，因而不能获得满分。使用差分只是快速统计，不代表已经正确处理重复使用优惠卡。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, p[N], cnt[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		fill(cnt, cnt + n + 1, 0);
		for (int i = 1; i <= m; i ++) cin >> p[i];
		for (int i = 1; i < m; i ++) {
			int l = min(p[i], p[i + 1]), r = max(p[i], p[i + 1]);
			cnt[l] ++, cnt[r] --;
		}
		LL ans = 0;
		for (int i = 1; i < n; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			cnt[i] += cnt[i - 1];
			ans += 1LL * cnt[i] * min(a, b + c);
		}
		cout << ans << "\n";
	}
	return 0;
}

逐段模拟获得50分

测试点 $1\sim10$ 中 $N,M\le1000$。对每次行程直接遍历其经过的铁路，把计数 $x_i$ 加一。

一段铁路若从未经过，就不必买卡，费用为0。若经过 $x_i$ 次，不办卡共支付 $x_iA_i$；办卡只支付一次 $C_i$，之后每次价格为 $B_i$，合计 $C_i+x_iB_i$。两者取最小，各铁路互不影响，因此相加得到答案。

时间 $O(NM)$、空间 $O(N+M)$。多测最坏工作量是 $\sum N_tM_t$，这一档至多 $10^7$ 次左右的逐段操作。该做法对全范围答案仍正确，只是可能超时；代码没有主动拒绝较大的输入。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, p[N], cnt[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		fill(cnt, cnt + n + 1, 0);
		for (int i = 1; i <= m; i ++) cin >> p[i];
		for (int i = 1; i < m; i ++) {
			int l = min(p[i], p[i + 1]), r = max(p[i], p[i + 1]);
			for (int j = l; j < r; j ++) cnt[j] ++;
		}
		LL ans = 0;
		for (int i = 1; i < n; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			ans += min(1LL * cnt[i] * a, c + 1LL * cnt[i] * b);
		}
		cout << ans << "\n";
	}
	return 0;
}

满分：把行程看成区间加

一次从 $u$ 到 $v$ 的行程，使每条编号在

$$[\min(u,v),\max(u,v)-1]$$

内的铁路计数加一。对差分数组，在左端加一，在右端的后一位减一；全部行程处理完后求前缀和，便得到每段经过次数。

设 $l=\min(u,v)$、$r=\max(u,v)$，具体修改为 $d_l\mathrel{+}=1,d_r\mathrel{-}=1$。这里减的是 $d_r$，不是 $d_{r+1}$：编号 $r$ 的站点不是编号 $r$ 的铁路。

最后计算

$$\mathrm{ans}=\sum_{i=1}^{N-1}\min(x_iA_i,C_i+x_iB_i).$$

正确性证明

使用次数正确。 链上两站之间的必经铁路恰好组成上述区间。每次差分更新仅使这个区间前缀和增加一，故处理全部行程后的 $x_i$ 等于该铁路的总使用次数。

单条铁路选择最优。 不办卡的费用为 $x_iA_i$。一旦办卡，持卡价格始终小于直接价格，购卡提前到第一次使用之前不会更差，费用为 $C_i+x_iB_i$。不存在需要再考虑的第三种更优付费方式。

局部选择可合并。 每张卡只作用于一条铁路，且没有共同预算或购卡数量限制，所以不同铁路的付费选择相互独立。把每条铁路的最优费用相加就是全局最小费用。

复杂度与实现边界

每组时间 $O(N+M)$，空间 $O(N+M)$。可能存在约 $10^{15}$ 的答案，乘法及答案必须使用64位整数。没有经过的边取到 $\min(0,C_i)=0$，不能无条件支付所有办卡费；每组重新清空差分数组与答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, p[N], cnt[N];
int main() {
	freopen("rail.in", "r", stdin);
	freopen("rail.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		fill(cnt, cnt + n + 1, 0);
		for (int i = 1; i <= m; i ++) cin >> p[i];
		for (int i = 1; i < m; i ++) {
			int l = min(p[i], p[i + 1]), r = max(p[i], p[i + 1]);
			cnt[l] ++, cnt[r] --;
		}
		LL ans = 0;
		for (int i = 1; i < n; i ++) {
			int a, b, c;
			cin >> a >> b >> c;
			cnt[i] += cnt[i - 1];
			ans += min(1LL * cnt[i] * a, c + 1LL * cnt[i] * b);
		}
		cout << ans << "\n";
	}
	return 0;
}

自然错解与反例

• “持卡单价更低就办卡”忽略购卡费：一段只经过一次，$A=10,B=9,C=10$，直接支付10优于办卡19。
• “每段都不办卡”：$A=10,B=1,C=1$ 且经过一次，办卡仅2。
• “每次比较 $A$ 与 $B+C$”：$A=10,B=1,C=10$，行程为 $1,2,1,2$，即经过该段铁路三次，最优为 $10+3=13$，并非30。
• “已付直接票价攒到卡费后才买”：仍在上述例子中，先付10、下次办卡付11、再付1，共22；已知整段行程时应提前办卡。把这个策略用公式加速，错误也不会消失。

读到一次性费用和反复使用，应先累计总次数再决策；读到链上反复跨区间，应考虑差分。按路线，单次行程20分、直接模拟50分、差分100分。

双端编队 题解

简要题意

给出按到达顺序排列的 $N$ 个正整数，每个数依次放在当前队列的左端或右端，第一个数没有方向选择。对全部编队过程，求最终队列中严格上升子序列的最大长度 $L$，以及各编队过程中长度为 $L$ 的子序列数量总和，模 $10^9+7$；操作不同或所选位置不同均分别计数。每组 $N\le2\times10^5$、$a_i\le10^9$，至多 $10$ 组，同一文件 $\sum N\le4\times10^5$，每组输出两个整数。

一句话题解

以原下标最小的入选者为中心，合并后缀中向两侧延伸的最长单调链及其计数，用树状数组优化，再乘上未被选定方向的自由操作数。

完整题解

30 分：枚举编队过程

当 $N\le18$ 时，枚举第 $2$ 到第 $N$ 名队员分别加入哪一端，共 $2^{N-1}$ 种编队过程。对每种最终队伍，做一次普通的最长严格上升子序列计数 DP：设 $f_i$ 为以最终位置 $i$ 结尾的最长长度，$g_i$ 为达到这一长度的方案数；从所有 $j<i$ 且 $a_j<a_i$ 的位置转移，长度更大时覆盖计数，相同长度时累加计数。

每一个“编队过程与所选位置集合”只被枚举一次。把所有过程的结果合并，便能得到答案。时间复杂度为 $O(2^N N^2)$，辅助空间 $O(N)$。参考实现用全局数组保存显式搜索栈，不依赖过深递归；这并不改变算法复杂度。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, a[N], q[N * 2], f[N], g[N], side[N], best, cnt;
void check(int l, int r) {
	for (int i = 1; i <= n; i ++) {
		f[i] = g[i] = 1;
		for (int j = 1; j < i; j ++) {
			if (q[l + j - 1] >= q[l + i - 1]) continue;
			if (f[j] + 1 > f[i]) f[i] = f[j] + 1, g[i] = g[j];
			else if (f[j] + 1 == f[i]) g[i] = (g[i] + g[j]) % mod;
		}
		if (f[i] > best) best = f[i], cnt = g[i];
		else if (f[i] == best) cnt = (cnt + g[i]) % mod;
	}
}
void dfs() {
	int u = 2, l = N, r = N;
	side[u] = 0;
	while (u >= 2) {
		if (u > n) {
			check(l, r);
			u --;
			if (u >= 2) {
				if (side[u] == 1) l ++;
				else r --;
			}
		} else if (side[u] == 0) {
			side[u] = 1;
			q[-- l] = a[u];
			side[++ u] = 0;
		} else if (side[u] == 1) {
			side[u] = 2;
			q[++ r] = a[u];
			side[++ u] = 0;
		} else {
			side[u] = 0;
			u --;
			if (u >= 2) {
				if (side[u] == 1) l ++;
				else r --;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		best = cnt = 0;
		q[N] = a[1];
		dfs();
		cout << best << " " << cnt << "\n";
	}
	return 0;
}

50 分：找出最早入选者

直接枚举最终队伍太多，应改为描述一支上升小队自身的结构。设其成员中原到达下标最小的人为 $i$。其余被选队员都在 $i$ 之后到达：

• 号码小于 $a_i$ 的人必须加入左端，并且到达顺序中的号码严格递减，这样最终从左到右才严格递增。
• 号码大于 $a_i$ 的人必须加入右端，并且到达顺序中的号码严格递增。
• 号码等于 $a_i$ 的人不能加入这支小队。

令 $f_i$ 为从 $i$ 开始、沿原下标递增方向的最长严格递减链长度，$g_i$ 为同样定义的最长严格递增链长度；两者都包含 $i$。同时维护对应方案数 $c_i,d_i$。逆序枚举 $i$，再枚举 $j>i$，即可完成两套普通 DP。

固定中心 $i$ 的最优长度为

$$f_i+g_i-1,$$

两个方向中除中心外的元素值域不交，因此没有共同使用同一队员的冲突，链选择数可以相乘，为 $c_i d_i$。先对所有达到全局最大长度 $L$ 的中心累加这个乘积。

还没有计入不影响小队的编队操作，最后需乘 $2^{N-L}$，证明见下一节。平方 DP 的时间复杂度为 $O(N^2)$、空间复杂度为 $O(N)$，在 $N\le1000$ 时获得累计 $50$ 分。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, a[N], f[N], g[N], cf[N], cg[N], sf[N], sg[N];
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i];
		int best = 0, cnt = 0;
		sf[n + 1] = sg[n + 1] = 0;
		for (int i = n; i; i --) {
			f[i] = g[i] = cf[i] = cg[i] = 1;
			for (int j = i + 1; j <= n; j ++) {
#ifdef PRUNE
				if (sf[j] + 1 < f[i] && sg[j] + 1 < g[i]) break;
#endif
				if (a[j] < a[i]) {
					if (f[j] + 1 > f[i]) f[i] = f[j] + 1, cf[i] = cf[j];
					else if (f[j] + 1 == f[i]) cf[i] = (cf[i] + cf[j]) % mod;
				} else if (a[j] > a[i]) {
					if (g[j] + 1 > g[i]) g[i] = g[j] + 1, cg[i] = cg[j];
					else if (g[j] + 1 == g[i]) cg[i] = (cg[i] + cg[j]) % mod;
				}
			}
			sf[i] = max(f[i], sf[i + 1]);
			sg[i] = max(g[i], sg[i + 1]);
			int len = f[i] + g[i] - 1, ways = (LL)cf[i] * cg[i] % mod;
			if (len > best) best = len, cnt = ways;
			else if (len == best) cnt = (cnt + ways) % mod;
		}
		for (int i = 1; i <= n - best; i ++) cnt = (LL)cnt * 2 % mod;
		cout << best << " " << cnt << "\n";
	}
	return 0;
}

为什么乘 $2^{N-L}$

一次完整编队过程共有 $N-1$ 次左右二选一。对于固定的、人数为 $L$ 的小队，除最早入选者外，其余 $L-1$ 人必须按号码大小加入指定一端。这 $L-1$ 个方向确定后，其他方向都不会改变所选队员之间的相对顺序，所以仍有

$$N-1-(L-1)=N-L$$

个自由选择，恰好对应 $2^{N-L}$ 种编队过程。

这里不能草率地说“每个没选的人都有两个方向”：若第 $1$ 人没被选中，他本来就没有方向选择；但此时最早入选者自己的方向可以自由选择，二者恰好抵消。上述直接数 $N-1$ 个操作的证明避开了这个边界问题。

满分：树状数组优化转移

转移只关心已经处理的后缀中，号码小于或大于 $a_i$ 的最优状态。先对号码离散化，逆序扫描原序列：

• 第一棵树状数组查询比当前秩小的前缀，得到递减方向的最优后继。
• 第二棵树状数组使用反向秩，把严格大于当前号码的范围也变成前缀查询，得到递增方向的最优后继。

树状数组每个结点存一对数“最长长度、方案数”。合并时，长度不同只保留较长者；长度相同则将方案数相加并取模。没有后继时，空链长度为 $0$、方案数为 $1$。对当前元素必须先查询两棵树，再插入新状态，且不能把相等号码包括在严格转移中。

标程中查询得到的左右长度不含中心，因此合并长度写成 l.first + r.first + 1，与上节包含中心的 $f_i+g_i-1$ 完全一致。

正确性证明

任取一支被计数的小队，其原下标最小的成员唯一确定中心 $i$。加入左端的成员在最终队列中的相对顺序与到达顺序相反，加入右端的成员相对顺序不变，故它必然对应上述两条单调链。

反过来，任选一条合法左链和一条合法右链，按指定方向插入它们，就能构成一支严格上升小队。两链值域分离，不会抢用相同成员，所以两个方向的选择完全独立。逆序 DP 枚举全部后继，归纳可得每个中心的最优长度和链计数均正确；树状数组只加速相同的转移，不改变转移集合。

不同中心表示不同的最早入选成员，不会重复计数。各中心只累加达到全局最优长度的方案，再乘每个固定小队恰有的 $2^{N-L}$ 种自由编队方式，因此输出的长度与数量总和正确。

复杂度与实现边界

每组离散化、树状数组操作均为 $O(N\log N)$，空间 $O(N)$。不同组分别清空本组会使用的树状数组范围。计数按模数存 int，相乘时必须先转 LL；不要只在赋值目标处使用长整型。

容易失分的方向

1. 只考虑第 1 个到达的人作中心。 输入序列 100 2 3 1 4 中，以第 2 人为中心可以选出 1,2,3,4，第 1 人不能同时加入这个长度为 4 的小队。
2. 把相同号码的队员合并。 样例的两个 1 有不同身份，且加入方向也分别计数；答案不是 1 或 2。
3. 找到最优长度就只记一种方案。 1 2 2 3 中，两个号码为 2 的队员可以分别作为长度为 3 的小队成员。两支小队均有自由编队方向，总数为 4。
4. 漏掉自由操作因子，或统一少乘一个 2。 第一个人没有方向选择已经在 $N-1-(L-1)$ 中扣除，不能再扣一次。
5. 只增加几个候选中心修补。 最优中心可以出现在中间，甚至不在前后若干个位置中；应完整处理全部中心，而不是凭样例限定中心范围。

参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10, mod = 1e9 + 7;
int n, m, a[N], b[N], pw[N];
PII tr[2][N];
PII merge(PII a, PII b) {
	if (a.first != b.first) return a.first > b.first ? a : b;
	return {a.first, (a.second + b.second) % mod};
}
void add(int k, int x, PII v) {
	for (; x <= m; x += x & -x) tr[k][x] = merge(tr[k][x], v);
}
PII query(int k, int x) {
	PII ans = {0, 0};
	for (; x; x -= x & -x) ans = merge(ans, tr[k][x]);
	if (!ans.first) ans.second = 1;
	return ans;
}
int main() {
	freopen("deque.in", "r", stdin);
	freopen("deque.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	pw[0] = 1;
	for (int i = 1; i < N; i ++) pw[i] = (LL)pw[i - 1] * 2 % mod;
	int T;
	cin >> T;
	while (T --) {
		cin >> n;
		for (int i = 1; i <= n; i ++) cin >> a[i], b[i] = a[i];
		sort(b + 1, b + n + 1);
		m = unique(b + 1, b + n + 1) - b - 1;
		for (int i = 1; i <= m; i ++) tr[0][i] = tr[1][i] = {0, 0};
		PII ans = {0, 0};
		for (int i = n; i; i --) {
			int x = lower_bound(b + 1, b + m + 1, a[i]) - b;
			PII l = query(0, x - 1), r = query(1, m - x);
			ans = merge(ans, {l.first + r.first + 1, int((LL)l.second * r.second % mod)});
			add(0, x, {l.first + 1, l.second});
			add(1, m - x + 1, {r.first + 1, r.second});
		}
		cout << ans.first << " " << (LL)ans.second * pw[n - ans.first] % mod << "\n";
	}
	return 0;
}

航道改向（canal）题解

简要题意

每组给出一张 $N$ 个点、$M$ 条边的有向图，每条边有非负通行费 $C_i$ 和非负改向费 $D_i$。出发前至多把一条边永久反向，通行费不变，求从 $1$ 到 $N$ 再回到 $1$ 的通行费与改向费之和的最小值，无法往返输出 $-1$。允许重边但无自环；$N\le200$，$M\le5\times10^4$，$C_i\le10^6$，$D_i\le10^9$；至多 $10$ 组，$\sum N\le400$、$\sum M\le10^5$。

一句话题解

先选定往返的两条最短路径；不在其中的边用四组最短路距离直接计算，在其中的边才真正改向并重新跑最短路。

完整题解

20 分：枚举改向边，重新求最短路

先枚举“不改向”，再枚举改向第 $i$ 条边。固定这个选择后，整张图不再变化，最优去程和最优返程可以独立选择，所以当前费用就是

$$\operatorname{dist}(1,N)+\operatorname{dist}(N,1)+D_i.$$

不改向时最后一项为 $0$。若其中任一方向不连通，该选择无效。

对于前 $4$ 点，逐次从边表重新建立距离矩阵，再运行 Floyd 即可。每次把被选中的一条边交换端点，其他边照常加入；有重边时取最小通行费。时间 $O(MN^3+M^2)$，空间 $O(N^2+M)$。

这里不能先把重边合并成一条再丢掉其余信息。改向的是一条具体的航道，移除它之后，原方向可能还有其他航道可用。

累计 40 分：改用两次 Dijkstra

每次修改后，只需要从 $1$ 和 $N$ 出发的两次最短路，不需要全部点对距离。由于点数不大，可以用邻接矩阵与朴素 Dijkstra，每次 $O(N^2)$。

为避免每次重新扫描全部边，在每对端点 $(u,v)$ 上保存最小通行费、最小边的编号，以及除去这条具体边后的次小通行费。次小值允许与最小值相等：两条同权重边仍然是两条不同的边。

反向边 $i:u\to v$ 时：

1. 若它是 $(u,v)$ 的最小边，将该位置暂时改为次小值；否则原最小值不变。
2. 把 $(v,u)$ 的最小费用暂时更新为与 $C_i$ 的较小值。
3. 跑两次最短路并更新答案，再恢复这两个位置。

所有边都这样尝试，时间 $O(MN^2+M)$，可覆盖前 $8$ 点，累计 $40$ 分。仅按“改向费已经不小于当前答案”跳过部分边，不能改变一般范围下的最坏复杂度。

特殊性质 A：另外 20 分

相邻两条边的起点、终点和通行费相同。反向其中一条时，另一条仍可提供原方向的同等通行能力。因此，这一性质下的修改，等价于只新增一条反向边。

对一般的单程 $s\to t$，若新增 $v\to u$，费用为 $c$，新最短距离为

$$\min\bigl(d(s,t),\ d(s,v)+c+d(u,t)\bigr).$$

第一项不使用新边，第二项使用新边。边权非负，因此最短路不需要反复使用它。

预处理从 $1$、从 $N$、到 $1$、到 $N$ 的四组距离。其中“到某点”可以在反图上跑最短路得到。枚举一条边时，用上式分别计算往返两程，再加上该边的改向费。时间 $O(N^2+M)$，空间 $O(N^2+M)$。

这条做法本身保证测试点 $9\sim12$ 的 $20$ 分。如果小 $M$ 时使用完整枚举，其他情况使用上述公式，则可以取得前 $12$ 点的 $60$ 分。不能在普通图上直接使用该公式：反向还会删除原边，原最短路径可能因此失效。

100 分：把必须重算的边限制到两条路径上

下面解决普通图中的删边影响。

在原图中，任意选定一条 $1\to N$ 最短路径，以及一条 $N\to1$ 最短路径。不连通的方向不选路径。把它们包含的边称为关键边。可以选取不重复顶点的最短路径，因此关键边至多 $2N-2$ 条；零权边不会破坏这个结论。

• 如果当前边是关键边，就真正反向并重新跑两次 Dijkstra。
• 如果不是关键边，就仍然使用上一节的四距离公式。

关键在于证明第二种情况不会错误地使用已被删除的边。

为什么非关键边可以直接套公式

只讨论单程 $s\to t$。选定的原最短路径不经过待反向边 $e:u\to v$，所以删除 $e$ 后，这条路径依然合法，距离 $d(s,t)$ 保持可行。

设公式的另一项为

$$X=d(s,v)+C_i+d(u,t).$$

它对应“原图最短路 $s\to v$，新边 $v\to u$，原图最短路 $u\to t$”的拼接。

如果两段原图最短路都不经过 $e$，这个拼接在改向后的图中合法，可能有重复顶点，但删去非负环即可得到不更贵的路径。

如果第一段原图最短路经过 $u\to v$，把它在 $u$ 处截断，再接上原来的 $u\to t$ 最短路，就得到一条原图中的 $s\to t$ 路线。其费用不会超过 $X$，因为原拼接额外包含从 $u$ 到 $v$、再从 $v$ 回到 $u$ 的非负费用。于是 $X\ge d(s,t)$。

如果第二段经过 $u\to v$，同理可以直接将第一段 $s\to v$ 接到第二段从 $v$ 到 $t$ 的后缀，得到原图中费用不超过 $X$ 的路线，仍有 $X\ge d(s,t)$。

因此，只要拼接用了被删除的原边，它就不可能优于仍然合法的原最短路径；只有真正合法的拼接才可能改善答案。取两项最小值不会低估实际距离。

若原本 $s\to t$ 不连通，上面的截断过程会推出一条原图中的可达路线，产生矛盾，所以任何有限的拼接都不会使用被删除的边，此时公式仍成立。

反过来，改向后的最短路径若不使用新边，其费用不小于原距离；若使用新边，分为前后两段后，其费用不小于 $X$。故公式也不会高估，得到的就是修改后的真实最短距离。

正确性与复杂度

算法枚举了不改向以及所有可能的改向边。关键边的结果由修改后的图上直接求最短路得到；非关键边的结果已由上述证明保证正确。固定改向选择后，去程与返程可以独立取最短路，所以对所有选择取最小值就是全局最优答案。

四次预处理需要 $O(N^2)$；最多 $2N-2$ 条关键边各执行两次 $O(N^2)$ 最短路；其余边每条 $O(1)$。加上读入建图，总时间为 $O(N^3+M)$，空间为 $O(N^2+M)$。

实现时通过 Dijkstra 的前驱边恢复一条最短路径。只在严格变短时更新前驱，并且不更新已经确定最短路的点；即使有零权边，前驱关系也不会形成环。保存边的编号，不能只保存两个端点，否则无法区分重边。

距离用 long long，无穷大取远大于合法答案、又能安全相加的值。每组清空边权矩阵、次小值与关键边标记；临时修改后必须恢复原值。

一种不能误判为超复杂度的加强做法

也可以先用“仅添加反向边”的公式，为每条改向操作求一个费用下界，按下界从小到大排序，再逐条真正改向验证。若下一条的下界已不小于当前答案，就可以停止。

非关键边的下界等于真实费用；第一次检查到非关键边后，剩余下界都不更小，可以立即终止。此前可能产生不准确下界的边最多只有 $2N-2$ 条，所以实际重新跑最短路的次数仍为 $O(N)$。这是合法满分算法，复杂度 $O(N^3+M\log M)$，不能将它作为“带剪枝暴力”要求卡掉。

常见错误与赛时取分

• 只新增逆边，不移除原边。 仅在特殊性质 A 下成立；一般图中可能算出原本无法完成的往返。
• 只枚举最短路径上的边。 关键边只是需要重算，不代表只有关键边有改向价值。例如某条目前很少使用的单向通道，反向后可能变成极便宜的捷径。
• 只按去程选边。 同一次改向也会影响返程，甚至切断返程；两程必须在同一张修改后的图中计算。
• 按改向费只试前几条。 改向费小不代表通行费用改善大；试前八条等局部修补同样没有正确性保证。
• 删掉同向全部重边。 题目只改向指定的一条，其他航道仍在。
• 漏掉不改向。 某些图的最优方案就是保持原状，所有改向费用都为正时尤应注意。

赛时先用完整枚举争取 $40$ 分，再补特殊性质 A 即可累计 $60$ 分。满分部分应从“哪一些边的删除会破坏原最短路”出发，而不是反复为逐边重算添加没有复杂度保证的剪枝。

参考实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 210, M = 5e4 + 10;
const LL inf = 1LL << 60;
int n, m, u[M], v[M], c[M], w[M];
int id[N][N], pre[N], last[N];
LL g[N][N], second[N][N], d[4][N], dis[N];
bool st[N], key[M];
void dijkstra(int s, LL dist[], bool rev) {
	for (int i = 1; i <= n; i ++) dist[i] = inf, st[i] = false, pre[i] = last[i] = 0;
	dist[s] = 0;
	for (int k = 1; k <= n; k ++) {
		int x = 0;
		for (int i = 1; i <= n; i ++)
			if (!st[i] && (!x || dist[i] < dist[x])) x = i;
		if (!x || dist[x] == inf) break;
		st[x] = true;
		for (int y = 1; y <= n; y ++) {
			LL len = rev ? g[y][x] : g[x][y];
			if (!st[y] && dist[y] > dist[x] + len) {
				dist[y] = dist[x] + len;
				pre[y] = x;
				last[y] = rev ? id[y][x] : id[x][y];
			}
		}
	}
}
void mark(int x) {
	while (pre[x]) {
		key[last[x]] = true;
		x = pre[x];
	}
}
int main() {
	freopen("canal.in", "r", stdin);
	freopen("canal.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++)
			for (int j = 1; j <= n; j ++) g[i][j] = second[i][j] = inf, id[i][j] = 0;
		for (int i = 1; i <= m; i ++) {
			cin >> u[i] >> v[i] >> c[i] >> w[i];
			key[i] = false;
			int x = u[i], y = v[i];
			if (c[i] < g[x][y]) {
				second[x][y] = g[x][y];
				g[x][y] = c[i], id[x][y] = i;
			} else second[x][y] = min(second[x][y], (LL)c[i]);
		}
		dijkstra(1, d[0], false), mark(n);
		dijkstra(n, d[1], false), mark(1);
		dijkstra(1, d[2], true);
		dijkstra(n, d[3], true);
		LL ans = min(inf, d[0][n] + d[1][1]);
		for (int i = 1; i <= m; i ++) {
			int x = u[i], y = v[i];
			LL a, b;
			if (!key[i]) {
				a = min(d[0][n], d[0][y] + c[i] + d[3][x]);
				b = min(d[1][1], d[1][y] + c[i] + d[2][x]);
			} else {
				LL old1 = g[x][y], old2 = g[y][x];
				g[x][y] = second[x][y];
				g[y][x] = min(g[y][x], (LL)c[i]);
				dijkstra(1, dis, false), a = dis[n];
				dijkstra(n, dis, false), b = dis[1];
				g[x][y] = old1, g[y][x] = old2;
			}
			ans = min(ans, a + b + w[i]);
		}
		cout << (ans == inf ? -1 : ans) << "\n";
	}
	return 0;
}

独距城市（unique）题解

简要题意

每组给出一棵 $N$ 个城市的无权树，以及各城在 $[1,M]$ 中的特产编号。对每个城市 $x$，找出所有与它的距离在其他城市中仅出现一次的城市，再统计这些城市的不同特产种数，逐个输出 $N$ 个答案。$2\le N\le2\times10^5$、$1\le M\le N$；至多 $10$ 组，$\sum N\le4\times10^5$。需要区分“这个距离只有一座城市”和“这个距离只有一种特产”：前者才符合题意。

一句话题解

以直径两端分别为根，先遍历最高子树，用候选栈删去旁支造成的等距离冲突并维护特产频次，逐点取两次统计的较大值。

完整题解

20 分：逐个城市重新计算距离

固定观察点 $x$，执行一次 BFS，求出所有点到 $x$ 的距离。令 $num[d]$ 为距离等于 $d$ 的城市数，同时记录该层的某座城市 $who[d]$。对于 $d\ge1$，只有 $num[d]=1$ 时，$who[d]$ 才是独距城市；将其特产编号放进布尔数组去重即可。

每次 BFS 和统计都是 $O(N)$，枚举所有观察点总时间 $O(N^2)$、额外空间 $O(N)$。这是一条直接而可靠的 20 分路线，不需要任何直径性质；不能只在第一次 BFS 后反复使用同一份距离。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> e[N];
int n, m, c[N], d[N], num[N], who[N], q[N];
bool used[N];
int main() {
	freopen("unique.in", "r", stdin);
	freopen("unique.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) e[i].clear();
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
		}
		for (int i = 1; i <= n; i ++) cin >> c[i];
		for (int s = 1; s <= n; s ++) {
			for (int i = 0; i <= n; i ++) d[i] = -1, num[i] = 0, used[i] = false;
			int hh = 1, tt = 1, ans = 0;
			q[1] = s, d[s] = 0;
			while (hh <= tt) {
				int u = q[hh ++];
				for (int v : e[u]) {
					if (d[v] != -1) continue;
					d[v] = d[u] + 1, q[++ tt] = v;
					num[d[v]] ++, who[d[v]] = v;
				}
			}
			for (int i = 1; i < n; i ++)
				if (num[i] == 1 && !used[c[who[i]]]) used[c[who[i]]] = true, ans ++;
			cout << ans << "\n";
		}
	}
	return 0;
}

从“所有距离层”转向一条路径

对观察点 $x$，选一个离它最远的点 $D$。每个独距城市都在路径 $x\leadsto D$ 上。

证明：设点 $y$ 不在这条路径上，$p$ 是从 $y$ 接入这条路径的位置。由 $D$ 最远可知

$$\operatorname{dist}(x,p)+\operatorname{dist}(p,y) \le \operatorname{dist}(x,D).$$

因此，从 $p$ 沿路径向 $D$ 走 $\operatorname{dist}(p,y)$ 条边，一定能走到另一座城市 $z$，并满足 $\operatorname{dist}(x,z)=\operatorname{dist}(x,y)$。所以 $y$ 不独距。

树的任意一条直径的两个端点记为 $D_1,D_2$。标准直径性质保证：对任意 $x$，$D_1,D_2$ 中至少一个是 $x$ 的最远点。于是分别以 $D_1,D_2$ 为根计算即可。

固定根 $D$ 后，我们只统计观察点 $x$ 的严格祖先中真正独距的点。即使这个 $D$ 不是 $x$ 的最远点，得到的也是真实答案的一个子集，不会高估；而两个根中至少有一次包含全部独距城市。因此最终对同一点取两次答案的 最大值，不是相加。

旁支究竟排除哪些祖先

以 $D$ 为根，令 $dep[u]$ 表示点 $u$ 的深度，$h[u]$ 表示 $u$ 子树中的最大向下距离。

沿着根到观察点 $x$ 的路径考虑一座城市 $u$。某条不在这条路径上的旁支从 $u$ 向外延伸了 $L$ 条边，则旁支中到 $u$ 距离为 $1,2,\ldots,L$ 的城市都存在。它们分别与 $u$ 向根方向第 $1,2,\ldots,L$ 个祖先到 $x$ 的距离相同。

所以，这条旁支会排除深度区间

$$[\max(0,dep[u]-L),\ dep[u]-1]$$

内的祖先。多个旁支只需取最大长度。

• 从 $u$ 进入孩子 $v$ 时，旁支长度是 $u$ 的其他孩子子树的最大高度；
• 在 $x$ 本身统计答案时，旁支长度是 $h[x]$；
• $x$ 不计入候选，因为题目不允许把自身当作独距城市。

单色的另外 20 分：只维护最早仍可能保留的祖先

当 $M=1$ 时，只要存在一个独距城市，答案就是 $1$；否则为 $0$。

在固定根的遍历过程中，不需要保存全部候选祖先，只维护其中最小的深度 $low[u]$。根没有严格祖先，可令其值为无穷大。

从 $u$ 进入孩子 $v$，设其他孩子旁支的最大长度为 $L$。这次只会删除候选深度的一个后缀：

$$low[v]= \begin{cases} low[u],&low[u]<dep[u]-L,\\ dep[u],&\text{否则}. \end{cases}$$

第二种情况表示原候选全部被排除，但 $u$ 自己成为 $v$ 的候选祖先。到点 $u$ 统计答案时，再考虑它的整个子树：存在独距祖先，当且仅当 $low[u]<dep[u]-h[u]$。

预处理最高、次高孩子子树即可 $O(1)$ 得到 $L$；两次遍历总时间 $O(N)$、空间 $O(N)$。这档需要先理解直径与旁支模型，不应当被视为免费分。与小树 BFS 按性质分别处理，可以累计 40 分。

特产全异的另外 20 分：回滚遍历与区间覆盖

当 $C_i=i$ 时，不同特产数就是独距城市的数量。先不追求线性做法，而是直接维护前面推导出的排除区间。

以路径深度为下标，维护覆盖次数数组 $b$。每出现一条旁支，给相应排除区间加 $1$；离开这条旁支所对应的递归分支时减 $1$。对于当前 $x$，只查询深度 $0\sim dep[x]-1$，其中覆盖次数为 $0$ 的位置就是独距祖先。

使用线段树维护区间最小值、最小值出现次数和加法懒标记。覆盖次数始终非负，所以区间最小值等于 $0$ 时，其出现次数正是所需数量。每条树边只对应常数次区间操作，总时间 $O(N\log N)$、空间 $O(N)$。

这种方法不需要发现满分算法的“最高孩子优先”，但也有完整的建模和实现难度。与小树 BFS 合并可以累计 40 分；再加入单色分支，可以累计 60 分。

下面一份程序提供这些路线。将 MODE 设为 $1,2,3,4,5$，分别对应：仅单色、仅全异、小树加单色、小树加全异、三档合并。MODE=1,2 直接使用对应的特殊性质公式，在其他性质下不保证答案正确。MODE=3,4,5 则先判断所支持的特殊性质，不满足时仍执行完整的逐根 BFS：小树能通过，大树可能超时。默认 MODE=5 对应 60 分组合，不通过主动退出伪装部分分。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> e[N];
int n, m, c[N], ans[N], fa[N], dep[N], q[N], h[N], son[N], sec[N], pos[N], low[N];
int d[N], num[N], who[N];
bool used[N];
int mn[N * 4], tag[N * 4], sum[N * 4];
#ifndef MODE
#define MODE 5
#endif
int build(int root) {
	q[1] = root, fa[root] = 0, dep[root] = 0;
	int hh = 1, tt = 1;
	while (hh <= tt) {
		int u = q[hh ++];
		for (int v : e[u]) {
			if (v == fa[u]) continue;
			fa[v] = u, dep[v] = dep[u] + 1, q[++ tt] = v;
		}
	}
	for (int i = n; i >= 1; i --) {
		int u = q[i];
		h[u] = son[u] = sec[u] = 0;
		for (int v : e[u]) {
			if (v == fa[u]) continue;
			int len = h[v] + 1;
			if (len > h[u]) sec[u] = h[u], h[u] = len, son[u] = v;
			else sec[u] = max(sec[u], len);
		}
	}
	return q[n];
}
int single(int root) {
	int far = build(root);
	low[root] = n;
	for (int i = 1; i <= n; i ++) {
		int u = q[i];
		if (low[u] < dep[u] - h[u]) ans[u] = 1;
		for (int v : e[u]) {
			if (v == fa[u]) continue;
			int len = son[u] == v ? sec[u] : h[u];
			low[v] = low[u] < dep[u] - len ? low[u] : dep[u];
		}
	}
	return far;
}
void pushup(int u) {
	mn[u] = min(mn[u * 2], mn[u * 2 + 1]);
	sum[u] = (mn[u * 2] == mn[u] ? sum[u * 2] : 0)
		+ (mn[u * 2 + 1] == mn[u] ? sum[u * 2 + 1] : 0);
}
void init(int u, int l, int r) {
	mn[u] = tag[u] = 0, sum[u] = r - l + 1;
	if (l == r) return;
	int mid = (l + r) / 2;
	init(u * 2, l, mid), init(u * 2 + 1, mid + 1, r);
}
void pushdown(int u) {
	if (!tag[u]) return;
	for (int v = u * 2; v <= u * 2 + 1; v ++) mn[v] += tag[u], tag[v] += tag[u];
	tag[u] = 0;
}
void change(int u, int l, int r, int a, int b, int x) {
	if (a <= l && r <= b) {
		mn[u] += x, tag[u] += x;
		return;
	}
	pushdown(u);
	int mid = (l + r) / 2;
	if (a <= mid) change(u * 2, l, mid, a, b, x);
	if (b > mid) change(u * 2 + 1, mid + 1, r, a, b, x);
	pushup(u);
}
void update(int u, int len, int x) {
	int l = max(0, dep[u] - len), r = dep[u] - 1;
	if (l <= r) change(1, 0, n - 1, l, r, x);
}
int query(int u, int l, int r, int last) {
	if (mn[u] > 0) return 0;
	if (r <= last) return sum[u];
	pushdown(u);
	int mid = (l + r) / 2, res = query(u * 2, l, mid, last);
	if (last > mid) res += query(u * 2 + 1, mid + 1, r, last);
	return res;
}
int distinct(int root) {
	int far = build(root);
	init(1, 0, n - 1);
	for (int i = 1; i <= n; i ++) pos[i] = -1;
	int u = root;
	while (u) {
		if (pos[u] == -1) {
			update(u, h[u], 1);
			if (dep[u]) ans[u] = max(ans[u], query(1, 0, n - 1, dep[u] - 1));
			update(u, h[u], -1);
			pos[u] = 0;
		}
		int v = 0;
		while (pos[u] < (int)e[u].size()) {
			int t = e[u][pos[u] ++];
			if (t != fa[u]) {
				v = t;
				break;
			}
		}
		if (v) {
			update(u, son[u] == v ? sec[u] : h[u], 1);
			u = v;
		} else {
			int p = fa[u];
			if (p) update(p, son[p] == u ? sec[p] : h[p], -1);
			u = p;
		}
	}
	return far;
}
void brute() {
	for (int s = 1; s <= n; s ++) {
		for (int i = 0; i <= n; i ++) d[i] = -1, num[i] = 0, used[i] = false;
		int hh = 1, tt = 1;
		q[1] = s, d[s] = 0;
		while (hh <= tt) {
			int u = q[hh ++];
			for (int v : e[u]) {
				if (d[v] != -1) continue;
				d[v] = d[u] + 1, q[++ tt] = v;
				num[d[v]] ++, who[d[v]] = v;
			}
		}
		for (int i = 1; i < n; i ++)
			if (num[i] == 1 && !used[c[who[i]]]) used[c[who[i]]] = true, ans[s] ++;
	}
}
int main() {
	freopen("unique.in", "r", stdin);
	freopen("unique.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) e[i].clear(), ans[i] = 0;
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
		}
		bool all = m == n;
		for (int i = 1; i <= n; i ++) cin >> c[i], all &= c[i] == i;
		bool a = MODE == 1 || ((MODE == 3 || MODE == 5) && m == 1);
		bool b = MODE == 2 || ((MODE == 4 || MODE == 5) && all);
		if (a || b) {
			int root = build(1);
			if (a) single(single(root));
			else distinct(distinct(root));
		} else brute();
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}

满分：让删除变成单调的

一般情况下，需要对未覆盖的祖先特产去重，单纯查询线段树中有几个零已经不够。换一个遍历顺序，可以完全不做回滚。

维护一只候选栈，栈内节点按根到当前点的顺序排列，因此深度严格递增。当前栈只包含尚未被旁支排除的严格祖先。

在每个点 $u$，首先遍历高度最大的孩子，其余孩子按任意顺序遍历：

1. 准备进入孩子 $v$ 时，设其他孩子的最大旁支长度为 $L$；弹出栈顶所有满足 $dep[z]\ge dep[u]-L$ 的祖先。
2. 把 $u$ 加入栈，再遍历 $v$。
3. 从 $v$ 返回时，如果 $u$ 仍在栈顶，将它弹出；不恢复此前删除的其他祖先。
4. 全部孩子处理结束后，用 $h[u]$ 再删除一次后缀，此时栈中就是 $u$ 的独距祖先，记录不同特产数。

步骤 3 为什么不需要恢复，是本题最关键的一步。

设最高孩子的高度（包含从 $u$ 到孩子的那条边）为 $H$。最先进入它时，其他旁支的最大高度是次高值；从它出来后，再进入任何其他孩子时，这棵最高子树本身成为旁支，于是应排除 $u$ 向根方向长达 $H$ 的祖先。

在此前最高子树内部，若一个节点 $p$ 的旁支长为 $L$，则从 $u$ 出发到这条旁支尽头的长度不超过 $H$。因此，它造成的任何祖先排除，都不会越过深度 $dep[u]-H$ 这一界线。返回 $u$ 时，用最高旁支进行的后缀删除已经覆盖了这些影响，所以那些祖先在后续孩子中也不可能重新成为候选。其他孩子高度均不超过 $H$，同理不会制造需要恢复的祖先。

更具体地，令 $a=\operatorname{dist}(u,p)$，就有 $a+L\le H$。内部删除区间的最低深度满足

$$dep[p]-L=dep[u]+a-L\ge dep[u]-H+2a\ge dep[u]-H,$$

因此确实不会删到后续本应恢复的更浅祖先。

所以每个节点只需先找到最高孩子，并求次高值，不必把所有孩子排序。离开 $u$ 的整棵子树前，用 $h[u]$ 排除后，状态也恰好适用于返回父亲的过程。

颜色维护、复杂度与实现边界

用 $cnt[c]$ 记录当前栈中编号 $c$ 的特产出现次数，另设 $kinds$ 表示次数非零的特产种数。入栈时由 $0$ 变 $1$ 则增加种数；出栈时由 $1$ 变 $0$ 则减少种数。

每条树边下降时只入栈一次，出栈总次数不超过入栈次数；所有邻接表的扫描总长度为 $2(N-1)$。两次计算都是 $O(N)$，总空间 $O(N)$。

实现时注意：

• 最高高度相同时，任取一个最高孩子即可；次高高度必须保留相等情况。
• 冲突条件是 $dep[z]\ge dep[u]-L$，不能写成严格大于。
• 两个根得到的特产集合可能重叠，最后取最大值而非相加。
• 颜色编号可能未全部出现，不能把 $M$ 当作实际种类数。
• 链的长度可达 $2\times10^5$，下面用显式游标模拟 DFS，不依赖系统递归栈。
• 多组数据重新清空邻接表、频次与答案；答案上界为 $N-1$，使用 int 足够。

常见错误方向

“只看最远城市”会遗漏更近的唯一距离层。例如一棵至少有三片叶子的星形树，对任意叶子而言，中心城市是独距城市，尽管最远的其他叶子并不唯一。

“独距城市一定在固定直径上”也不正确：对于长旁支末端的观察点，旁支上的祖先可能是独距城市。正确结论是它们位于观察点到某个最远点的路径上，这条路径不一定包含于事先选择的那条直径。

任意孩子顺序却直接删除且不恢复候选，会把当前分支造成的影响错误带到之后更高的分支；尝试正反两种输入顺序不能代替最高孩子优先的证明。

满分参考实现

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
vector<int> e[N];
int n, m, c[N], ans[N], fa[N], dep[N], q[N];
int h[N], son[N], sec[N], pos[N], st[N], cnt[N], top, kinds;
int build(int root) {
	int hh = 1, tt = 1;
	q[1] = root, fa[root] = 0, dep[root] = 0;
	while (hh <= tt) {
		int u = q[hh ++];
		for (int v : e[u]) {
			if (v == fa[u]) continue;
			fa[v] = u, dep[v] = dep[u] + 1;
			q[++ tt] = v;
		}
	}
	return q[n];
}
void pop() {
	if (!-- cnt[c[st[top --]]]) kinds --;
}
void trim(int limit) {
	while (top && dep[st[top]] >= limit) pop();
}
int solve(int root) {
	int far = build(root);
	for (int i = n; i >= 1; i --) {
		int u = q[i];
		h[u] = son[u] = sec[u] = 0, pos[u] = -1;
		for (int v : e[u]) {
			if (v == fa[u]) continue;
			int len = h[v] + 1;
			if (len > h[u]) sec[u] = h[u], h[u] = len, son[u] = v;
			else sec[u] = max(sec[u], len);
		}
	}
	int u = root;
	while (u) {
		int v = 0, len;
		if (pos[u] == -1) {
			pos[u] = 0;
			v = son[u], len = sec[u];
		} else {
			if (top && st[top] == u) pop();
			len = h[u];
			while (pos[u] < (int)e[u].size()) {
				int t = e[u][pos[u] ++];
				if (t != fa[u] && t != son[u]) {
					v = t;
					break;
				}
			}
		}
		if (v) {
			// 先走最高子树，之后旁支造成的删除范围不会缩小。
			trim(dep[u] - len);
			st[++ top] = u;
			if (!cnt[c[u]] ++) kinds ++;
			u = v;
		} else {
			trim(dep[u] - h[u]);
			ans[u] = max(ans[u], kinds);
			u = fa[u];
		}
	}
	return far;
}
int main() {
	freopen("unique.in", "r", stdin);
	freopen("unique.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0);
	int T;
	cin >> T;
	while (T --) {
		cin >> n >> m;
		for (int i = 1; i <= n; i ++) e[i].clear(), ans[i] = cnt[i] = 0;
		top = kinds = 0;
		for (int i = 1; i < n; i ++) {
			int u, v;
			cin >> u >> v;
			e[u].push_back(v), e[v].push_back(u);
		}
		for (int i = 1; i <= n; i ++) cin >> c[i];
		int a = build(1), b = solve(a);
		solve(b);
		for (int i = 1; i <= n; i ++) cout << ans[i] << "\n";
	}
	return 0;
}