树中可以形成回文的路径数

6942. 树中可以形成回文的路径数

给你一棵树（即，一个连通、无向且无环的图），根节点为 0 ，由编号从 0 到 n - 1 的 n 个节点组成。这棵树用一个长度为 n 、下标从 0 开始的数组 parent 表示，其中 parent[i] 为节点 i 的父节点，由于节点 0 为根节点，所以 parent[0] == -1 。

另给你一个长度为 n 的字符串 s ，其中 s[i] 是分配给 i 和 parent[i] 之间的边的字符。s[0] 可以忽略。

找出满足 u < v ，且从 u 到 v 的路径上分配的字符可以 重新排列 形成回文的所有节点对 (u, v) ，并返回节点对的数目。

如果一个字符串正着读和反着读都相同，那么这个字符串就是一个回文。

示例 1：

输入：parent = [-1,0,0,1,1,2], s = "acaabc"
输出：8
解释：符合题目要求的节点对分别是：
- (0,1)、(0,2)、(1,3)、(1,4) 和 (2,5) ，路径上只有一个字符，满足回文定义。
- (2,3)，路径上字符形成的字符串是 "aca" ，满足回文定义。
- (1,5)，路径上字符形成的字符串是 "cac" ，满足回文定义。
- (3,5)，路径上字符形成的字符串是 "acac" ，可以重排形成回文 "acca" 。

示例 2：

输入：parent = [-1,0,0,0,0], s = "aaaaa"
输出：10
解释：任何满足 u < v 的节点对 (u,v) 都符合题目要求。

提示：

n == parent.length == s.length
1 <= n <= 10⁵
对于所有 i >= 1 ，0 <= parent[i] <= n - 1 均成立
parent[0] == -1
parent 表示一棵有效的树
s 仅由小写英文数字组成

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: long long countPalindromePaths(vector<int>& parent, string s) { } };

cpp 解法, 执行用时: 584 ms, 内存消耗: 142.8 MB, 提交时间: 2023-07-24 11:17:00

class Solution {
public:
    void dfs(const vector<vector<int>>& graph, const string& s, unordered_map<int, int>& cnt, long long& ans, int u, int sum) {
        for (int i = 0;i < 26;++i) {
            const auto it = cnt.find(sum ^ (1 << i));
            if (it != cnt.end()) ans += it->second;
        }
        ans += cnt[sum]++;
        for (int v : graph[u])
            dfs(graph, s, cnt, ans, v, sum ^ (1 << (s[v] - 'a')));
    }
    
    long long countPalindromePaths(const vector<int>& parent, string s) {
        const int n = parent.size();
        vector<vector<int>> graph(n);
        for (int i = 1;i < n;++i)
            graph[parent[i]].push_back(i);
        unordered_map<int, int> cnt;
        long long ans = 0;
        dfs(graph, s, cnt, ans, 0, 0);
        return ans;
    }
};

java 解法, 执行用时: 430 ms, 内存消耗: 92.1 MB, 提交时间: 2023-07-24 11:16:31

class Solution {
    private List<int[]>[] g;
    private Map<Integer, Integer> cnts;
    private long res;

    public long countPalindromePaths(List<Integer> parent, String s) {
        int n = parent.size();
        this.g = new ArrayList[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int i = 1; i < n; ++i) {
            g[parent.get(i)].add(new int[] { i, 1 << (s.charAt(i) - 'a' )});
        }
        this.cnts = new HashMap<>();
        dfs(0, 0);
        return res;

    }

    private void dfs(int x, int xor) {
        res += cnts.getOrDefault(xor, 0);
        for (int i = 0; i < 26; ++i) {
            res += cnts.getOrDefault(xor ^ (1 << i), 0);
        }
        cnts.merge(xor, 1, Integer::sum);
        for (int[] neighbor : g[x]) {
            int y = neighbor[0];
            int m = neighbor[1];
            dfs(y, xor ^ m);
        }
    }
}

golang 解法, 执行用时: 256 ms, 内存消耗: 39.4 MB, 提交时间: 2023-07-24 11:15:39

func countPalindromePaths(parent []int, s string) int64 {
	n := len(parent)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		p := parent[i]
		g[p] = append(g[p], i)
	}

	ans := 0
	cnt := map[int]int{0: 1} // 一条「空路径」
	var dfs func(int, int)
	dfs = func(v, xor int) {
		for _, w := range g[v] {
			x := xor ^ (1 << (s[w] - 'a'))
			ans += cnt[x] // x ^ x = 0
			for i := 0; i < 26; i++ {
				ans += cnt[x^(1<<i)] // x ^ (x^(1<<i)) = 1<<i
			}
			cnt[x]++
			dfs(w, x)
		}
	}
	dfs(0, 0)
	return int64(ans)
}

python3 解法, 执行用时: 2628 ms, 内存消耗: 153.2 MB, 提交时间: 2023-07-24 11:15:19

class Solution:
    def countPalindromePaths(self, parent: List[int], s: str) -> int:
        n = len(s)
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parent[i]].append(i)

        ans = 0
        cnt = Counter([0])  # 一条「空路径」
        def dfs(v: int, xor: int) -> None:
            nonlocal ans
            for w in g[v]:
                bit = 1 << (ord(s[w]) - ord('a'))  # 26个字母奇偶性
                x = xor ^ bit
                ans += cnt[x] + sum(cnt[x ^ (1 << i)] for i in range(26))
                cnt[x] += 1
                dfs(w, x)
        dfs(0, 0)
        return ans

上一题

下一题

详情