芭芭拉冲鸭~

NC213789. 芭芭拉冲鸭~

描述

芭芭拉拿到了一棵无根树，树上每个节点被染成了红色或绿色或蓝色。（R=红色，G=绿色，B=蓝色）。

任意两点之间的距离均为1。

若一条边连接的两个节点的颜色不同，芭芭拉则可以在这条边上冲刺。

但是，芭芭拉在冲刺的时候不能掉头。例如芭芭拉已经从 $x\$ 冲到 $y\$ 了，就不能再回到 $x\$ 。

现在芭芭拉想知道，自己在这棵树上最远能冲刺的距离是多少？

输入描述

第一行一个正整数，代表树的节点个数。
第二行是一个长度为的字符串，仅由"R、G、B"这三种字符组成。第i个字符用于描述第i个节点的颜色。
接下来的行，每行有两个正整数和，代表和节点有一条边连接。保证输入一定表示一棵树。

输出描述

一个正整数，代表芭芭拉能冲刺的距离的最大值。

示例1

输入:

5
RRGBG
1 2
2 3
3 4
4 5

输出:

说明:

这棵树是一条1-2-3-4-5的链，选择路径2-3-4-5即可。这样芭芭拉直接从2冲到5，冲刺距离为3。

注意1和2的颜色相同，所以芭芭拉并不能在1-2这条边上冲刺。

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

Python3 解法, 执行用时: 1021ms, 内存消耗: 116152K, 提交时间: 2022-11-02 12:20:59

import sys
sys.setrecursionlimit(100010)
n=int(input())
color=input()
child=[[] for i in range(n+1)]
for i in range(1,n):
    x,y=map(int,input().split())
    child[x].append(y)
    child[y].append(x)
dp=[0 for i in range(n+1)]
res = 0
def dfs(n,m):
    global res
    for i in child[n]:
        if i==m:continue
        dfs(i,n)
        if color[i-1]==color[n-1]:continue
        res=max(res,dp[i]+dp[n]+1)
        dp[n]=max(dp[n],dp[i]+1)
dfs(1,0)
print(res)

上一题

下一题

详情