跳转至

3331. 修改后子树的大小

来源第 142 场双周赛 Q2难度中等分数2045

题目描述

给你一棵 n 个节点且根节点为编号 0 的树,节点编号为 0 到 n - 1 。这棵树用一个长度为 n 的数组 parent 表示,其中 parent[i] 是第 i 个节点的父亲节点的编号。由于节点 0 是根,parent[0] == -1 。

给你一个长度为 n 的字符串 s ,其中 s[i] 是节点 i 对应的字符。

对于节点编号从 1 到 n - 1 的每个节点 x ,我们 同时 执行以下操作 一次 :

  • 找到距离节点 x 最近 的祖先节点 y ,且 s[x] == s[y] 。
  • 如果节点 y 不存在,那么不做任何修改。
  • 否则,将节点 x 与它父亲节点之间的边 删除 ,在 x 与 y 之间连接一条边,使 y 变为 x 新的父节点。

请你返回一个长度为 n 的数组 answer ,其中 answer[i] 是 最终 树中,节点 i 为根的 子树 的 大小 。

 

示例 1:

输入:parent = [-1,0,0,1,1,1], s = "abaabc"

输出:[6,3,1,1,1,1]

解释:

节点 3 的父节点从节点 1 变为节点 0 。

示例 2:

输入:parent = [-1,0,4,0,1], s = "abbba"

输出:[5,2,1,1,1]

解释:

以下变化会同时发生:

  • 节点 4 的父节点从节点 1 变为节点 0 。
  • 节点 2 的父节点从节点 4 变为节点 1 。

 

提示:

  • n == parent.length == s.length
  • 1 <= n <= 105
  • 对于所有的 i >= 1 ,都有 0 <= parent[i] <= n - 1 。
  • parent[0] == -1
  • parent 表示一棵合法的树。
  • s 只包含小写英文字母。

解法

方法一

思考

每个节点可改挂到最近的、字母相同的祖先之下。 \(n \le 10^5\),不能先显式改边再另做一遍子树统计。

一次 DFS 即可:用栈 \(d[c]\) 记录字母 \(c\) 的祖先链。回溯前若存在更近的同字母祖先,则把当前子树大小加到该祖先上,否则加到父节点。

后序保证 \(\textit{ans}[i]\) 已含全部后代;弹栈后祖先链恢复,互不干扰。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def findSubtreeSizes(self, parent: list[int], s: str) -> list[int]:
        def dfs(i: int, fa: int):
            ans[i] = 1
            d[s[i]].append(i)
            for j in g[i]:
                dfs(j, i)
            k = fa
            if len(d[s[i]]) > 1:
                k = d[s[i]][-2]
            if k != -1:
                ans[k] += ans[i]
            d[s[i]].pop()

        n = len(s)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)
        d = defaultdict(list)
        ans = [0] * n
        dfs(0, -1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    private List<Integer>[] g;
    private List<Integer>[] d;
    private char[] s;
    private int[] ans;

    public int[] findSubtreeSizes(int[] parent, String s) {
        int n = s.length();
        g = new List[n];
        d = new List[26];
        this.s = s.toCharArray();
        Arrays.setAll(g, k -> new ArrayList<>());
        Arrays.setAll(d, k -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parent[i]].add(i);
        }
        ans = new int[n];
        dfs(0, -1);
        return ans;
    }

    private void dfs(int i, int fa) {
        ans[i] = 1;
        int idx = s[i] - 'a';
        d[idx].add(i);
        for (int j : g[i]) {
            dfs(j, i);
        }
        int k = d[idx].size() > 1 ? d[idx].get(d[idx].size() - 2) : fa;
        if (k >= 0) {
            ans[k] += ans[i];
        }
        d[idx].remove(d[idx].size() - 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> findSubtreeSizes(vector<int>& parent, string s) {
        int n = s.size();
        vector<int> g[n];
        vector<int> d[26];
        for (int i = 1; i < n; ++i) {
            g[parent[i]].push_back(i);
        }
        vector<int> ans(n);
        auto dfs = [&](this auto&& dfs, int i, int fa) -> void {
            ans[i] = 1;
            int idx = s[i] - 'a';
            d[idx].push_back(i);
            for (int j : g[i]) {
                dfs(j, i);
            }
            int k = d[idx].size() > 1 ? d[idx][d[idx].size() - 2] : fa;
            if (k >= 0) {
                ans[k] += ans[i];
            }
            d[idx].pop_back();
        };
        dfs(0, -1);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func findSubtreeSizes(parent []int, s string) []int {
    n := len(s)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        g[parent[i]] = append(g[parent[i]], i)
    }
    d := [26][]int{}
    ans := make([]int, n)
    var dfs func(int, int)
    dfs = func(i, fa int) {
        ans[i] = 1
        idx := int(s[i] - 'a')
        d[idx] = append(d[idx], i)
        for _, j := range g[i] {
            dfs(j, i)
        }
        k := fa
        if len(d[idx]) > 1 {
            k = d[idx][len(d[idx])-2]
        }
        if k != -1 {
            ans[k] += ans[i]
        }
        d[idx] = d[idx][:len(d[idx])-1]
    }
    dfs(0, -1)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function findSubtreeSizes(parent: number[], s: string): number[] {
    const n = parent.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    const d: number[][] = Array.from({ length: 26 }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push(i);
    }
    const ans: number[] = Array(n).fill(1);
    const dfs = (i: number, fa: number): void => {
        const idx = s.charCodeAt(i) - 97;
        d[idx].push(i);
        for (const j of g[i]) {
            dfs(j, i);
        }
        const k = d[idx].length > 1 ? d[idx].at(-2)! : fa;
        if (k >= 0) {
            ans[k] += ans[i];
        }
        d[idx].pop();
    };
    dfs(0, -1);
    return ans;
}

方法二:显式栈

思考

每个节点可改挂到最近的、字母相同的祖先之下。 \(n\) 可以到 \(10^5\),不能先改边再另做一遍子树统计。一条链上第一次递归总是走向唯一的孩子,深度就是 \(n\),会超出默认递归上限。

子树大小要等后代都统计完才能加到新的父节点上,同字母祖先只出现在当前路径上。

因此用显式栈做后序,并用 \(d[c]\) 记录字母 \(c\) 仍在路径上的结点。进入时把自身大小记为 \(1\) 并压入字母栈,再压入离开标记和孩子。离开时若字母栈里还有更早的同字母结点,就把当前子树大小加到它上面,否则加到父亲,然后弹出字母栈。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def findSubtreeSizes(self, parent: list[int], s: str) -> list[int]:
        n = len(s)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)
        d = [[] for _ in range(26)]
        ans = [0] * n
        stk = [(0, -1, 0)]
        while stk:
            i, fa, state = stk.pop()
            if state == 0:
                ans[i] = 1
                idx = ord(s[i]) - 97
                d[idx].append(i)
                stk.append((i, fa, 1))
                for j in g[i]:
                    stk.append((j, i, 0))
            else:
                idx = ord(s[i]) - 97
                k = d[idx][-2] if len(d[idx]) > 1 else fa
                if k != -1:
                    ans[k] += ans[i]
                d[idx].pop()
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int[] findSubtreeSizes(int[] parent, String s) {
        int n = s.length();
        List<Integer>[] g = new List[n];
        List<Integer>[] d = new List[26];
        Arrays.setAll(g, k -> new ArrayList<>());
        Arrays.setAll(d, k -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parent[i]].add(i);
        }
        int[] ans = new int[n];
        char[] cs = s.toCharArray();
        Deque<int[]> stk = new ArrayDeque<>();
        stk.push(new int[] {0, -1, 0});
        while (!stk.isEmpty()) {
            int[] cur = stk.pop();
            int i = cur[0], fa = cur[1], state = cur[2];
            int idx = cs[i] - 'a';
            if (state == 0) {
                ans[i] = 1;
                d[idx].add(i);
                stk.push(new int[] {i, fa, 1});
                for (int j : g[i]) {
                    stk.push(new int[] {j, i, 0});
                }
            } else {
                int k = d[idx].size() > 1 ? d[idx].get(d[idx].size() - 2) : fa;
                if (k >= 0) {
                    ans[k] += ans[i];
                }
                d[idx].remove(d[idx].size() - 1);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<int> findSubtreeSizes(vector<int>& parent, string s) {
        int n = s.size();
        vector<vector<int>> g(n);
        vector<int> d[26];
        for (int i = 1; i < n; ++i) {
            g[parent[i]].push_back(i);
        }
        vector<int> ans(n);
        vector<array<int, 3>> stk{{0, -1, 0}};
        while (!stk.empty()) {
            auto cur = stk.back();
            stk.pop_back();
            int i = cur[0], fa = cur[1], state = cur[2];
            int idx = s[i] - 'a';
            if (state == 0) {
                ans[i] = 1;
                d[idx].push_back(i);
                stk.push_back({i, fa, 1});
                for (int j : g[i]) {
                    stk.push_back({j, i, 0});
                }
            } else {
                int k = d[idx].size() > 1 ? d[idx][d[idx].size() - 2] : fa;
                if (k >= 0) {
                    ans[k] += ans[i];
                }
                d[idx].pop_back();
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
func findSubtreeSizes(parent []int, s string) []int {
    n := len(s)
    g := make([][]int, n)
    for i := 1; i < n; i++ {
        g[parent[i]] = append(g[parent[i]], i)
    }
    d := [26][]int{}
    ans := make([]int, n)
    stk := [][3]int{{0, -1, 0}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        i, fa, state := cur[0], cur[1], cur[2]
        idx := int(s[i] - 'a')
        if state == 0 {
            ans[i] = 1
            d[idx] = append(d[idx], i)
            stk = append(stk, [3]int{i, fa, 1})
            for _, j := range g[i] {
                stk = append(stk, [3]int{j, i, 0})
            }
        } else {
            k := fa
            if len(d[idx]) > 1 {
                k = d[idx][len(d[idx])-2]
            }
            if k != -1 {
                ans[k] += ans[i]
            }
            d[idx] = d[idx][:len(d[idx])-1]
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function findSubtreeSizes(parent: number[], s: string): number[] {
    const n = parent.length;
    const g: number[][] = Array.from({ length: n }, () => []);
    const d: number[][] = Array.from({ length: 26 }, () => []);
    for (let i = 1; i < n; ++i) {
        g[parent[i]].push(i);
    }
    const ans: number[] = Array(n).fill(0);
    const stk: number[][] = [[0, -1, 0]];
    while (stk.length) {
        const [i, fa, state] = stk.pop()!;
        const idx = s.charCodeAt(i) - 97;
        if (state === 0) {
            ans[i] = 1;
            d[idx].push(i);
            stk.push([i, fa, 1]);
            for (const j of g[i]) {
                stk.push([j, i, 0]);
            }
        } else {
            const k = d[idx].length > 1 ? d[idx][d[idx].length - 2] : fa;
            if (k >= 0) {
                ans[k] += ans[i];
            }
            d[idx].pop();
        }
    }
    return ans;
}

评论