3331. 修改后子树的大小

找到距离节点x最近的祖先节点y，且s[x]==s[y]。然后将x连到y上.

题解

维护这个换父节点这个要求，所以需要从顶到下(只执行一次)dfs。同时维护路径上的每个字母对应的最新节点，初始化成一个全为-1的数组，表示(a-z)都是没有最新出现的。递归到x节点时，更新最新出现的位置，a[s[x]]=x。

对于节点x及其子节点y如果a[s[y]]!=-1(说明前面s[y]这个字符一定出现过)。把y这个节点连到a[s[y]]这节点上，成为其子节点。同时把x的子节点y改成-1(说明已经把y移除了)。在第二次dfs(记录结果)中，不去递归等于-1的儿子。

注意写回溯递归返回前，要恢复a[s[x]]的原始值(递归到x之前的值)

第二次dfs

写一个自底向上的DFS，返回子树的大小。

当前子树大小为1(当前节点)，加上所有子树的大小之和。

class Solution {
public:
    void f(string& s,vector<int>& a,vector<vector<int> >& dp,int x){
        int sx= s[x]-'a';
        int old = a[sx];//为之后回溯做准备
        a[sx]=x;//上一个祖先更新
        for(int i=dp[x].size()-1;i>=0;i--){//遍历子节点
            int y=dp[x][i];//子元素
            int tmp=a[s[y]-'a'];//找这个元素之前出现过没
            if(tmp!=-1){//如果之前出现过这个元素。
                dp[tmp].push_back(y);//将这个放在tmp上
                dp[x][i]=-1;// 删除y
            }
            f(s,a,dp,y);
        }
        a[sx]=old;
    }
    vector<int> findSubtreeSizes(vector<int>& parent, string s) {
        int n=parent.size();
        vector<vector<int> > dp(n);
        for(int i=1;i<n;i++){//第一个根节点为-1，不用管。
            dp[parent[i]].push_back(i);//记录子节点
        }
        vector<int> a(26,-1);
        // function<void(int)> f = [&](int x){
        //     int sx= s[x]-'a';
        //     int old = a[sx];//为之后回溯做准备
        //     a[sx]=x;//上一个祖先更新
        //     for(int i=dp[x].size()-1;i>=0;i--){//遍历子节点
        //         int y=dp[x][i];//子元素
        //         int tmp=a[s[y]-'a'];//找这个元素之前出现过没
        //         if(tmp!=-1){//如果之前出现过这个元素。
        //             dp[tmp].push_back(y);//将这个放在tmp上
        //             dp[x][i]=-1;// 删除y
        //         }
        //         f(y);
        //     }
        //     a[sx]=old;
        // };    
        f(s,a,dp,0);
        vector<int> ans(n,1);//注意这里把当前节点算进去
        auto dfs = [&](auto&& dfs,int x) -> void {
            for(int y: dp[x]){
                if(y!=-1){
                    dfs(dfs,y);
                    ans[x]+=ans[y];
                }
            }
        };
        dfs(dfs,0);
        return ans;
    }
};

也可以直接一次dfs自底向上，就是在维护的同时维护树的大小。

如果将y连到a[s[y]]上，就将其树大小加到a[s[y]]上

如果y没有连到a[s[y]]上，那么说明它还连在原本节点x上，也就加到x上。

最后别忘了回溯

class Solution {
public:
    vector<int> findSubtreeSizes(vector<int>& parent, string s) {
        int n=parent.size();
        vector<vector<int> > dp(n);
        for(int i=1;i<n;i++){//第一个根节点为-1，不用管。
            dp[parent[i]].push_back(i);//记录子节点
        }
        vector<int> ans(n,1);//注意这里把当前节点算进去
        vector<int> a(26,-1);

        auto dfs = [&](auto&& dfs,int x) -> void {
            int sx= s[x]-'a';
            int old = a[sx];//为之后回溯做准备
            a[sx]=x;//上一个祖先更新
            for(int y: dp[x]){
                dfs(dfs,y);
                int tmp=a[s[y]-'a'];
                if(tmp==-1){//没出现过
                    ans[x]+=ans[y];//就是保持不动还连在原本的父节点上
                }else {
                    ans[tmp]+=ans[y];//换父节点
                }
            }
            a[sx]=old;
        };
        dfs(dfs,0);
        return ans;
    }
};