问题：Leetcode 2246. 相邻字符不同的最长路径
给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 ，这棵树由编号从 0 到 n - 1 的 n 个节点组成。用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树，其中 parent[i] 是节点 i 的父节点，由于节点 0 是根节点，所以 parent[0] == -1 。
另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符。
请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 ，并返回该路径的长度。
算法：
考虑用树形 DP 求直径。枚举子树 x 的所有子树 y，维护从 x 出发的最长路径 max_len，那么可以更新答案为从 y 出发的最长路径加上 max_len，再加上 1（边 x − y），即合并从 x 出发的两条路径。递归结束时返回 max_len。
对于本题的限制，我们可以在从子树 y 转移过来时，仅考虑从满足 s [ y ] != s [ x ] 的子树 y 转移过来，所以对上述做法加个 if 判断就行了。
由于本题求的是 点的个数 ，所以答案为最长路径的长度加 1 。
时间复杂度：O(n) 。
空间复杂度：O(n) 。
代码：
class Solution {
public:int longestPath(vector<int>& parent, string s) {int n = parent.size();vector<vector<int>> tree(n); // 两个维度，第一维度为下标，第二维度为孩子的下标for (int i = 1; i < n; i++)tree[parent[i]].emplace_back(i);int ans = 0; // 最长路径长度=最高子树高度+次高子树高度，可以通过遍历取大值实现// return 以x为起点的路径长度auto dfs = [&](auto &&dfs,int x) -> int{int max_len = 0; // 一个节点不形成路径，初始化长度为0for (int y : tree[x]) {int y_len = dfs(dfs,y) + 1;// 每一条以x为起点的路径长度为y的长度+1if (s[x] != s[y]) {ans = max(ans, max_len + y_len); // 更新答案为前面的最大链长+当前最大链长max_len = max(max_len, y_len); // 更新最大链长}}return max_len;};dfs(dfs,0);return ans + 1;}
};
