1519. 子树中标签相同的节点数

1519. 子树中标签相同的节点数

树形dp

class Solution {
public:
    vector<vector<int>>f;
    vector<vector<int>>g;
    string w;

    vector<int> countSubTrees(int n, vector<vector<int>>& edges, string labels) {
        f=vector<vector<int>>(n,vector<int>(26));
        g=vector<vector<int>>(n,vector<int>());
        w=labels;

        for(auto e:edges){
            int a=e[0],b=e[1];
            g[a].push_back(b),g[b].push_back(a);
        }
        
        dfs(0,-1);
        vector<int> res(n);
        for(int i=0;i<res.size();i++)res[i]=f[i][w[i]-'a'];

        return res;
    }

    void dfs(int u,int fa){
        f[u][w[u]-'a']=1;

        for(auto son:g[u]){
            if(son==fa)continue;
            dfs(son,u);
            for(int j=0;j<26;j++)
                f[u][j]+=f[son][j];
        }
    }
};