塔子哥是一位研究者,他在研究网络传输时遇到了一个问题。
他拿到了一张通讯网络的拓扑结构图,其中每条通讯线路被染成了红色或者蓝色。
默认以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⊕1]+1).所以我们需要先知道所有子节点的dp值,再用子节点的dp值去更新父节点。这个我们用dfs去处理。
扫码备注加群即可,期待您的到来~