题目内容

塔子哥是一位研究者，他在研究网络传输时遇到了一个问题。

他拿到了一张通讯网络的拓扑结构图，其中每条通讯线路被染成了红色或者蓝色。

思路

默认以1为根节点进行$dfs$遍历。

$dp[i][0]$表示在以$i$为根节点的子树中，且与$i$的连边为蓝色所有路径中最长的。$dp[i][1]$表示以$i$为根节点的子树中，与$i$的连边为红色的所有路径中最长的。那从前面两个$dp$我们可以知道以$i$为根节点，且选择了节点$i$的最长路径肯定是$dp[i][0]+dp[i][1]$。那假如我们讨论了所有子树，那么最长路径也肯定知道了。

现在问题在于如何得到所有节点的$dp$值呢。我们发现假如我们知道了一个节点u的所有子节点$v$的$dp$值，那么$u$的$dp$值也就知道了。因为节点$u$的$dp[u][x]=max(dp[v][x\oplus 1]+1)$.所以我们需要先知道所有子节点的$dp$值，再用子节点的$dp$值去更新父节点。这个我们用$dfs$去处理。

代码