首页 > 试题广场 >

树的最大权值

[编程题]树的最大权值
  • 热度指数：16 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红定义一棵树的权值为:
若一条简单路径 u\rightarrow v 满足 s_u+...+s_v 是一个回文串。在所有这样的路径中，路径的长度的最大值是是该树的权值。
现在小红给定一棵结点总数为 n 的树和 'a','b','c',...,'z'每种字母的个数，保证所有个数之和恰好等于 n。
你需要将每个字母填入一个树的结点，使得该树的权值最大，输出树的最大权值。

输入描述:
第一行输入一个长度为26的数组，表示每个字母的个数，保证总和为 n。

第二行输入一个整数 n(1\leq n\leq 10^5)，表示树的结点总数。

接下来 n-1 行，每行输入两个整数 u,v(1\leq u,v\leq n,u\neq v)，表示树的一条边。


输出描述:
输出一个整数，表示树的最大权值。
示例1

输入

1 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
5
1 2
2 3
3 4
4 5

输出

3
算法知识视频讲解
添加回答
C++
黄良头像 黄良
路径长度的定义不是边的数量吗？答案是按照点的数量来的？
发表于 2025-07-03 18:13:00 回复(0)
提交观点

问题信息

难度：
1条回答 22浏览

热门推荐

相关试题

树的最大权值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号