Readme

1857.Largest-Color-Value-in-a-Directed-Graph

首先一張圖里是否有环，这个容易判断。我们现在只考虑这张图没有环的情况，也就是这张图里的每个连通区域都是树。

显然，为了最大化题目所求的最大元素频次，我们显然会希望这个路径尽量地长，这样才能经过更多的节点，增多每个元素的频次。所以我们必然会找那些入度为零的节点作为路径起点。

如果这条路径没有分叉，那么我们在前进的过程中只要维护一个长度为26的计数器就行，用来记录从路径起点到该节点时所经过的字符频次。接下来一个关键的问题是，假如有一条路径到A时的频次统计是count1，另一条路径到B时的频次统计是count2，而且A和B都会指向C，那么我们如何设置C的频次统计？此时我们并不清楚，C的频次统计是应该继承自A还是B，这是因为我们不知道最终哪个字符的频次会最大。可能在count1里面字母a出现得最多，在count2里面字母b出现得最多；如果最终全局来看a的频次最多，那么C应该继承自count1，以最大化a的频次；否则就应该继承自count2.

所以我们这里就会发现，如果不知道我们关注的究竟是哪个字符，那么在这个交叉点上的选择会很纠结。所以这就提示我们，不妨将“关注的字符”给固定下来。将原本的问题变成26个子问题，分别求一条路径里出现a的最多频次、一条路径里出现b的最多频次、一条路径里出现c的最多频次... 对于每个子问题，我们用拓扑排序（考察当前入度是否为零）来遍历所有节点，时间复杂度为o(N)。此时重新回顾上面的问题，C节点应该继承自哪个路径？取决于考察的字符ch，只需贪心地选count1和count2中ch的频次更多的那个。

将问题拆解之后，整体的复杂度就是O(26N). 但是仍有case会遇到TLE。改进的方法是指考察colors里面出现过的字符，而不用26个字符都跑一遍。