给出一棵 个节点以 1为根的树节点 的颜色为 现在对于每个结点 询问以 为根的子树里一共出现了多少种不同的颜色支持离线考虑预处理后 (1)输出答案可以发现每个节点的答案由其子树和其本身得到我们可以先预处理出每个节点子树的大小和它的重儿子重儿子同树链剖分一样是拥有节点最多子树的儿子这个过程显然可以 ()完成我们用 表示颜色 的出现次数表示结点 的答案遍历一个节点 我们按以下的步骤进行遍历先遍历 的轻非重儿子并计算答案但不保留遍历后它对 数组的影响遍历它的重儿子保留它对 数组的影响再次遍历 的轻儿子的子树结点加入这些结点的贡献以得到 的答案这样原本全部遍历两遍现在轻2遍重只需要1遍多层缩减下整体遍历数量接近Onlogn#include bits/stdc.h using namespace std; const int N 200005; vectorint g[N]; // 邻接表 int c[N]; // c[u] 表示节点 u 的颜色 int sz[N]; // 子树大小 int big[N]; // 重儿子 int cnt[N]; // 全局桶颜色出现次数 int diff; // 当前子树内不同颜色的数量 int ans[N]; // 最终答案 /** * 第一遍 DFS预处理子树大小和重儿子 */ void dfs1(int u, int fa) { sz[u] 1; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] sz[big[u]]) big[u] v; } } /** * 子树批量更新 * delta 1 表示加入-1 表示删除 */ void apply(int u, int fa, int delta) { int col c[u]; // 维护不同颜色数 if (cnt[col] 0 delta 1) diff; if (cnt[col] 1 delta -1) diff--; cnt[col] delta; // 递归处理整棵子树 for (int v : g[u]) { if (v fa) continue; apply(v, u, delta); } } /** * 第二遍 DFSDSU on Tree 主过程 * keep true 表示保留当前子树信息 * keep false 表示处理完后清空 */ void dfs2(int u, int fa, bool keep) { // 1. 递归处理所有轻儿子不保留 for (int v : g[u]) { if (v fa || v big[u]) continue; dfs2(v, u, false); } // 2. 处理重儿子保留 if (big[u]) dfs2(big[u], u, true); // 3. 合并把轻儿子子树重新加入 for (int v : g[u]) { if (v fa || v big[u]) continue; apply(v, u, 1); } // 4. 加入当前节点 apply(u, fa, 1); // 5. 记录答案 ans[u] diff; // 6. 如果是轻儿子整体撤销 if (!keep) apply(u, fa, -1); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; // 读入颜色 for (int i 1; i n; i) cin c[i]; // 读入树边 for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } // DSU on Tree dfs1(1, 0); dfs2(1, 0, true); // 输出答案 for (int i 1; i n; i) cout ans[i] \n[i n]; return 0; }