P6695 - 旅行

内存限制：512 MB 时间限制：3 S

题面：传统评测方式：文本比较上传者：

提交：3 通过：1

有一棵

n 个结点的无根树，每个结点都有对应的类型

ci 和权重

wi ，你需要在这棵树上规划若干次旅行。对于一次旅行，你将从一个树上的一个结点出发，沿着树上的边进行旅行，最终到达另一个和起点类型相同的结点。你会进行很多次旅行，但你希望对于每个结点，在所有旅行路线中最多只会经过一次。一次旅行的价值是起始点和终止点的权重和，你需要规划旅行的方案使得旅行的总权重和最大。

第一行输入一个正整数

t (1≤t≤3) 代表数据组数。

对于每组数据：

第一行输入一个正整数

n (1≤n≤2×105)，代表树的点数。

第二行输入

n 个正整数

ci (1≤ci≤n) ，代表每个结点的类型。

第三行输入

n 个正整数

wi (1≤wi≤n) ，代表每个结点的权重。

接下来

n−1 行每行两个正整数

ui,vi (1≤ui,vi≤n,ui≠vi) ,代表树上一条边，输入保证是一棵树。

输出一行一个正整数代表答案。

1
7
3 1 1 2 2 2 3
2 4 1 5 4 6 2
1 2
1 3
2 4 
2 5
3 6 
3 7

一种最优的旅行方案为：

旅行路线1：

4→2→5 ，价值为

9。

旅行路线2：

1→3→7，价值为

4。

价值总和为

13。

2024杭电多校第三场

6695: 旅行

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签