CF1029E Tree with Small Distances

    • 87通过
    • 179提交
  • 题目来源 CodeForces 1029E
  • 评测方式 RemoteJudge
  • 标签 动态规划,动规,dp 贪心 邻接表
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述

    给定一棵树。要求往树中加入一些边使得从1到其他节点的距离至多是2 。 输出加入边的最小数量。(边全部都是无向的)

    输入格式

    第一行一个整数n,表示树中的节点个数。 接下来n−1行,每行两个整数x,y,表示x,y之间有一条连边。

    输出格式

    输出一个整数,表示加入边的最小数量。

    数据范围

    对于30%的数据n≤10。对于70%的数据n≤100。对于100%的数据n≤105。

    题目描述

    You are given an undirected tree consisting of $ n $ vertices. An undirected tree is a connected undirected graph with $ n - 1 $ edges.

    Your task is to add the minimum number of edges in such a way that the length of the shortest path from the vertex $ 1 $ to any other vertex is at most $ 2 $ . Note that you are not allowed to add loops and multiple edges.

    输入输出格式

    输入格式:

    The first line contains one integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ) — the number of vertices in the tree.

    The following $ n - 1 $ lines contain edges: edge $ i $ is given as a pair of vertices $ u_i, v_i $ ( $ 1 \le u_i, v_i \le n $ ). It is guaranteed that the given edges form a tree. It is guaranteed that there are no loops and multiple edges in the given edges.

    输出格式:

    Print a single integer — the minimum number of edges you have to add in order to make the shortest distance from the vertex $ 1 $ to any other vertex at most $ 2 $ . Note that you are not allowed to add loops and multiple edges.

    输入输出样例

    输入样例#1: 复制
    7
    1 2
    2 3
    2 4
    4 5
    4 6
    5 7
    
    输出样例#1: 复制
    2
    
    输入样例#2: 复制
    7
    1 2
    1 3
    2 4
    2 5
    3 6
    1 7
    
    输出样例#2: 复制
    0
    
    输入样例#3: 复制
    7
    1 2
    2 3
    3 4
    3 5
    3 6
    3 7
    
    输出样例#3: 复制
    1
    

    说明

    The tree corresponding to the first example: The answer is $ 2 $ , some of the possible answers are the following: $ [(1, 5), (1, 6)] $ , $ [(1, 4), (1, 7)] $ , $ [(1, 6), (1, 7)] $ .

    The tree corresponding to the second example: The answer is $ 0 $ .

    The tree corresponding to the third example: The answer is $ 1 $ , only one possible way to reach it is to add the edge $ (1, 3) $ .

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。