leetcode5465

刷题主页

给你一棵树（即，一个连通的无环无向图），这棵树由编号从 0 到 n - 1 的 n 个节点组成，且恰好有 n - 1 条 edges 。树的根节点为节点 0 ，树上的每一个节点都有一个标签，也就是字符串 labels 中的一个小写字符（编号为 i 的 节点的标签就是 labels[i] ）
边数组 edges 以 edges[i] = [ai, bi] 的形式给出，该格式表示节点 ai 和 bi 之间存在一条边。
返回一个大小为 n 的数组，其中 ans[i] 表示第 i 个节点的子树中与节点 i 标签相同的节点数。
树 T 中的子树是由 T 中的某个节点及其所有后代节点组成的树。

记录一次微软的周赛，瞬间感觉自己弱到死，还有许多需要学习的知识。这道题算是常规题，无向图的遍历问题，通常这种直接套模板即可，具体解释结合代码讲解。

const int MAX=1e5+10;
//记录无向图的边，遇到无向图问题必须的有这一步
vector<int>Edges[MAX];
int cnt[MAX][26];
class Solution {
public:
//根据题目要求遍历无向图，递归实现。
    void dfs(vector<int>& res,int fa, string& labels,int root){
    //经过每个父节点时记录相关信息
        cnt[root][labels[root]-'a']++;
        //遍历每个节点的子节点
        for(int son:Edges[root]){
        //因为是无向图，所以不能再从父节点遍历回去
            if(son==fa)continue;
            //这道题是自底向上，因此需要先对子节点进行dfs
            dfs(res,root,labels,son);
            //根据子节点更新父节点信息
            for(int i=0;i<26;++i)cnt[root][i]+=cnt[son][i];
        }
        res[root]=cnt[root][labels[root]-'a'];
    }
    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        //初始化变量
        for(int i=0;i<n;++i){
            memset(cnt[i],0,sizeof(cnt[i]));
            Edges[i].clear();
        }
        //记录无向图的所有边，这是必须的
        for(const auto& temp:edges){
            Edges[temp[0]].push_back(temp[1]);
            Edges[temp[1]].push_back(temp[0]);
        }
        vector<int>res(n,0);
        dfs(res,-1,labels,0);
        return res;
    }
};