待补：有另解
看到维护树上问题，可以想到线段树合并。
但直接维护显然不行，要一点技巧。
发现 \(val\) 的出现次数 \(cnt_{val}\) 如果 \(\ge 3\)，那么一定是一个候选项，若 \(cnt_{val} = 1\)，那么一定不能作为候选项。
于是可以用权值线段树维护对于 \(val\) 有 \(cnt_{val} = 2\) 的 \(val\)。先离散化，然后再合并线段树。查找时，若右子节点的 \(\max = 2\) 或右子节点的 \(\min = 0\)，就递归查找右节点，反之亦然。若左右子节点都不满足，就返回 \(0\)，实现需要一点细节。
空间只需要开 \(32\) 倍。
时间复杂度：\(\mathcal{O}(n\log n)\)。
代码：
const int N = 1e5 + 10;
int n, tot, maxv, mx, num;
int a[N], b[N], rt[N], ans[N];
int head[N], cnt;
map<int, int> mp;
struct segt {
int ls, rs, mxv, mnv;
} tr[N << 5];
struct edge {
int v, nxt, id;
} e[N << 1];
void adde(int u, int v, int id) {
e[++cnt].v = v;
e[cnt].nxt = head[u];
e[cnt].id = id;
head[u] = cnt;
}
void pushup(int u) {
tr[u].mxv = max(tr[tr[u].ls].mxv, tr[tr[u].rs].mxv);
tr[u].mnv = min(tr[tr[u].ls].mnv, tr[tr[u].rs].mnv);
}
void ins(int u, int l, int r, int k, int val) {
if (l == r) {
tr[u].mxv = tr[u].mnv = val;
return;
}
int mid = l + r >> 1;
if (k <= mid)
ins(tr[u].ls = ++tot, l, mid, k, val);
else
ins(tr[u].rs = ++tot, mid + 1, r, k, val);
pushup(u);
}
int merge(int lu, int ru, int l, int r) {
if (!ru) return lu;
if (!lu) return ru;
if (l == r) {
tr[lu].mxv += tr[ru].mxv;
tr[lu].mnv += tr[ru].mnv;
return lu;
}
int mid = l + r >> 1;
tr[lu].ls = merge(tr[lu].ls, tr[ru].ls, l, mid);
tr[lu].rs = merge(tr[lu].rs, tr[ru].rs, mid + 1, r);
pushup(lu);
return lu;
}
int query(int u, int l, int r) {
if (l == r) {
if (tr[u].mxv == 2 || tr[u].mnv == 0)
return l;
return 0;
}
int mid = l + r >> 1;
if (tr[tr[u].rs].mxv == 2 || tr[tr[u].rs].mnv == 0)
return query(tr[u].rs, mid + 1, r);
if (tr[tr[u].ls].mxv == 2 || tr[tr[u].ls].mnv == 0)
return query(tr[u].ls, l, mid);
return 0;
}
void dfs(int u, int f, int pos) {
rt[u] = ++tot;
if (a[u])
ins(rt[u], 1, num, a[u], 1);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v != f) {
dfs(v, u, i);
if (tr[rt[v]].mxv)
rt[u] = merge(rt[u], rt[v], 1, num);
}
}
if (tr[rt[u]].mxv == 0) {
ans[e[pos].id] = max(mx, maxv);
return;
}
int val = max(maxv, b[query(rt[u], 1, num)]);
ans[e[pos].id] = val;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
adde(u, v, i), adde(v, u, i);
}
for (int i = 1; i <= n; i++)
cin >> a[i],
mp[a[i]]++;
for (auto it : mp) {
if (it.second == 2) {
b[++num] = it.first;
mx = max(mx, it.first);
} else if (it.second > 2)
maxv = max(maxv, it.first);
}
for (int i = 1; i <= n; i++)
if (mp[a[i]] != 2)
a[i] = 0;
else
a[i] = lower_bound(b + 1, b + num + 1, a[i]) - b;
dfs(1, 0, 0);
for (int i = 1; i < n; i++)
cout << ans[i] << "\n";
return 0;
}
提供一组 hack：
输入：
10
1 2
1 3
1 4
1 5
1 6
2 7
2 8
3 9
4 10
1 3 3 3 3 4 10 4 6 2
输出：
3
4
4
4
3
4
3
4
4