Every day a Leetcode

题目来源：2246. 相邻字符不同的最长路径

解法1：树形 DP

如果没有相邻节点的限制，那么本题求的就是树的直径上的点的个数，见于Leetcode543. 二叉树的直径。

考虑用树形 DP 求直径。

枚举子树 x 的所有子树 y，维护从 x 出发的最长路径 maxLen，那么可以更新答案为从 y 出发的最长路径加上 maxLen，再加上 1（边 x−>y），即合并从 x 出发的两条路径。递归结束时返回 maxLen。

对于本题的限制，我们可以在从子树 y 转移过来时，仅考虑从满足 s[y]≠s[x] 的子树 y 转移过来，所以对上述做法加个 if 判断就行了。

由于本题求的是点的个数，所以答案为最长路径的长度加 1。

代码：

/** @lc app=leetcode.cn id=2246 lang=cpp** [2246] 相邻字符不同的最长路径*/// @lc code=start
class Solution
{
public:int longestPath(vector<int> &parent, string s){int n = parent.size();vector<vector<int>> g(n);for (int i = 1; i < n; ++i)g[parent[i]].push_back(i);int ans = 0;function<int(int)> dfs = [&](int x) -> int{int maxLen = 0;for (int &y : g[x]){int len = dfs(y) + 1;if (s[y] != s[x]){ans = max(ans, maxLen + len);maxLen = max(maxLen, len);}}return maxLen;};dfs(0); // 根节点是节点 0return ans + 1;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n)，其中 n 是数组 parent 的长度。

空间复杂度：O(n)，其中 n 是数组 parent 的长度。