【深度优先搜索】【树】【状态压缩】2791. 树中可以形成回文的路径数

作者推荐

【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II

本文涉及知识点

深度优先搜索树图论状态压缩

LeetCode:2791. 树中可以形成回文的路径数

给你一棵树（即，一个连通、无向且无环的图），根节点为 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 仅由小写英文字母组成

深度优先搜索

树的路径一定是起点 $\rightarrow$ 公共祖先 $\rightarrow$ 终点，特例是起点（或终点）就是公共祖先。
且从 u 到 v 的路径上分配的字符可以重新排列形成回文 $\iff$ 各字符的数量只有1个是奇数或全部是偶数
状态压缩: mask &(1 << i ) 表示 ‘a’+i 出现的次数是奇数。

深度优先搜索的状态

暴力的办法是枚举左支和右支的状态，空间复杂度(2²⁶) 已经在超内存的边缘了。
状态优化：

在这里插入图片描述
如果node1到node2的路径能构成回文，那node1 $\rightarrow$ root $\rightarrow$ node2 也能构成回文。起点（或终点）就是公共祖先也符合。
单节点要排除，因为不符合v<v。

深度优先搜索的转移方程

vCnt[mask] 记录各节点到root（0）的mask。
node1的压缩状态为:mask
cnt += vCnt[mask]-1
cnt += $\sum_{j:0}^{25}vCnt[mask^(1<<j)]$

深度优先搜索的返回值

cnt/2。

代码

核心代码

class Solution {
public:
	long long countPalindromePaths(vector<int>& parent, string s) {
		m_s = s; 
		vector<vector<int>> vNeiBo(parent.size());
		for (int i = 1; i < parent.size(); i++)
		{
			vNeiBo[parent[i]].emplace_back(i);
		}
		DFS(vNeiBo, 0, -1, 0);
		long long llRet = 0;
		for (const auto& [mask, cnt] : m_mMaskCount)
		{
			llRet += cnt*(cnt - 1);
			for (int j = 0; j < 26; j++)
			{
				const int iNewMask = mask ^ (1 << j);
				if (m_mMaskCount.count(iNewMask))
				{
					llRet += cnt*m_mMaskCount[iNewMask];
				}
			}
		}
		return llRet / 2;
	}
	void DFS(vector<vector<int>>& neiBo, int cur, int par, int parMask)
	{
		parMask ^= (1 << (m_s[cur]-'a'));
		m_mMaskCount[parMask]++;
		for (const auto& next : neiBo[cur])
		{
			if (next == par)
			{
				continue;
			}
			DFS(neiBo, next, cur, parMask);
		}
	}
	unordered_map<int, long long> m_mMaskCount;
	string m_s;
};

测试用例

template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	vector<int> parent;
	string s;
	{
		Solution sln;
		parent = { -1, 0, 0, 1, 1, 2 }, s = "acaabc";
		auto res = sln.countPalindromePaths(parent, s);
		Assert(res,8);
	}

	{
		Solution sln;
		parent = { -1, 0, 0, 0, 0 }, s = "aaaaa";
		auto res = sln.countPalindromePaths(parent, s);
		Assert(res, 10);
	}
	
}

2023年11月版

class Solution{
public:
long long countPalindromePaths(vector&parent, string s) {
m_c = parent.size();
m_str = s;
m_vNeiBo.assign(m_c, vector());
for (int i = 0; i < 26; i++)
{
m_iVilidMask[i] = 1 << i;
}
m_llRet = 0;
m_mMaskNums.clear();
int iRoot = -1;
for (int i = 0; i < m_c; i++)
{
if (-1 == parent[i])
{
iRoot = i;
}
else
{
m_vNeiBo[parent[i]].emplace_back(i);
}
}
dfs(iRoot,0);
return m_llRet;
}
void dfs(int cur,int iMask)
{
const int curMask = iMask ^ ( 1 << (m_str[cur] - ‘a’));
for (int i = 0; i < 27; i++)
{
const int iNeedMask = m_iVilidMask[i] ^ curMask;
if (m_mMaskNums.count(iNeedMask))
{
m_llRet += m_mMaskNums[iNeedMask];
}
}
m_mMaskNums[curMask]++;
for (const auto& child : m_vNeiBo[cur])
{
dfs(child, curMask);
}
}
int m_iVilidMask[27] = { 0 };//记录所有字符都是偶数和只有一个字符是奇数
vector<vector> m_vNeiBo;
std::unordered_map<int,int> m_mMaskNums;
int m_c;
long long m_llRet = 0;//不包括单节点的合法路径数
string m_str;
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛