首页 > 试题广场 >

在树上游玩

[编程题]在树上游玩

热度指数：809 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的由 $n$ 个节点组成的无根树，每一条边都可以被染上颜色，初始时，全部边均为白色。
$\hspace{15pt}$ 现在，选中树上 $k$ 个不同的点，并将它们标记，随后，定义，如果一条树边 $(u, v)$ 满足节点 $u$ 和 $v$ 同时被标记，那么这条树边自动被染为红色，不需要花费任何代价。

$\hspace{15pt}$ 现在，你可以额外选择一些树边，将它们染成红色，每染一条边需要花费 $1$ 点代价。
$\hspace{15pt}$ 请你计算最小的染色代价，使得任意一个被标记的点都可以通过被染成红色的边到达至少一个未被标记的点。并输出不同的染色方案数量。

输入描述:

第一行输入两个整数  代表树的节点数、被标记的点数。
第二行输入  个不同的整数  代表被标记的点的编号。
此后  行，第  行输入两个整数  代表第  条树边连接  和 。

输出描述:

在一行上输出两个整数，代表最小的染色代价、满足条件的染色方案数量。由于染色方案数量可能很大，请输出对  取模后的结果。

示例1

输入

11 6
8 2 4 7 9 6
8 10
8 9
1 8
1 11
1 3
11 2
5 6
2 5
4 2
7 6

输出

3 4

说明

在这个样例中，树的形态如下图所示。

算法知识视频讲解

一个与众不同的字节

发表于 2025-04-15 23:18:04

感觉主要难点在于题意理解，其实就是图的遍历。把连通的标记节点视为一个连通块，每个连通块只需要染色一条边，总方案数为每个连通块相邻节点数的连乘，最小代价为连通块数量。 #include <iostream> #include <vector> using namespace s 展开全文

977ust

发表于 2025-04-04 18:55:46

#include <iostream> #include <vector> using namespace std; int main() { // int n,k; cin >> n >> k; // denot 展开全文

977ust

发表于 2025-04-04 19:22:14

#include <iostream> #include <vector> using namespace std; int main() { // int n,k; cin >> n >> k; // denot 展开全文

牛客856751393号

发表于 2025-03-14 16:01:37

from sys import stdin from collections import defaultdict # 计算从某个被标记的节点出发，不需要染色就能够到达的未被标记节点的数量 def dfs(node, parent): # (当前访问的节点，当前节点的父节点) vis 展开全文

牛客193507862号

发表于 2025-07-16 01:21:22

import sys from collections import deque # 最小染色数量，为红线(两个标记点有相连)的数量 # 方案数量,是与红线有相连的未染色边的数量，并除以模MOD # 由于染色方案数量可能很大，请输出对10^9+7取模后的结果 MOD = 10 ** 9 + 7 展开全文

emo的钝角天天摸鱼

发表于 2025-03-17 21:23:15

#include <iostream> #include <bits/stdc++.h> using namespace std; #define int long long unordered_map<int,int> mp1,mp2; // mp1记录节点展开全文

牛客193507862号

发表于 2025-07-15 03:05:50

import sys from collections import deque # 由于染色方案数量可能很大，请输出对10^9+7取模后的结果 MOD = 10 ** 9 + 7 def main(): input_l = sys.stdin.read().split() # 输展开全文

Goldminer

发表于 2025-04-25 10:49:56

#include <iostream> #include <vector> using namespace std; typedef long long LL; const int MOD = 1e9 + 7; const int maxn = 200005; bool vi 展开全文

番禺小韭菜

发表于 2025-03-06 11:57:42

#include <cstdint> #include <iostream> #include <vector> using namespace std; int main() { constexpr int MOD = 1e9 + 7; // 展开全文

牛客193507862号

发表于 2025-07-15 14:47:03

问题信息

动态规划

难度：

5条回答 39收藏 226浏览

在树上游玩

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题