首页 > 试题广场 >

小红的树权值

[编程题]小红的树权值
  • 热度指数：19 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小红这样定义一棵树的权值：对于一棵树，删除若干节点（删除节点指将该节点及其关联的所有边从图中移除）后满足剩余的所有联通块大小都为 1，可能的最小删除数量即为这棵树的权值。
\hspace{15pt}现在小红拿到了一棵以 1 号节点为根，包含 n 个点的有根树，她想知道这棵树中 1\sim n 号点的所有子树的权值分别是多少，请你帮帮她。

【名词解释】
\hspace{15pt}子树：对于树中某个节点，其与所有后代节点构成的集合称为该节点的子树。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 10^5 \right)。
\hspace{15pt}之后的 n - 1 行，每行输入两个整数 u,v \left(1 \leqq u, v \leqq n,u \ne v \right)，代表有一条边连接 u,v。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^5。


输出描述:
\hspace{15pt}对于每组测试数据，新起一行。

\hspace{15pt}在一行内输出 n 个整数，依次代表 1 \sim n 号节点的子树的权值。
示例1

输入

1
5
1 2
2 3
3 4
3 5

输出

2 1 1 0 0

说明

\hspace{15pt}以 1 号点为根的子树：删除 2,3 号节点后符合要求，权值为 2；
\hspace{15pt}以 2 号点为根的子树：删除 3 号节点后符合要求，权值为 1；
\hspace{15pt}以 3 号点为根的子树：删除 3 号节点后符合要求，权值为 1；
\hspace{15pt}以 4 号点为根的子树：初始状态已经符合要求，权值为 0；
\hspace{15pt}以 5 号点为根的子树：初始状态已经符合要求，权值为 0。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 57浏览

热门推荐

相关试题

小红的树权值

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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