算法
(树上dfs序) $O(N)$
发现一直没有人写去常数的做法
可以用树上 $\operatorname{dfs}$ 来统计从根节点开始且经过点 $v$ 的所有树链上的点对点 $v$ 的颜色 $c$ 的贡献,然后用它容斥掉从根节点开始到点 $v$ 的路径上的点对颜色 $c$ 的贡献,就能求出点 $v$ 的答案。
C++ 代码
class Solution {
public:
vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
vector<vector<int>> to(n);
for (auto e : edges) {
int a = e[0], b = e[1];
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> ans(n), cnt(26);
auto dfs = [&](auto& f, int v, int p=-1) -> void {
ans[v] = cnt[labels[v]-'a']++;
for (int u : to[v]) {
if (u == p) continue;
f(f, u, v);
}
ans[v] = cnt[labels[v]-'a']-ans[v];
};
dfs(dfs, 0);
return ans;
}
};