题目详情题解（0）讨论（0）提交记录（0）

AT_arc125_f.[ARC125F] Tree Degree Subset Sum

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵包含 NN 个顶点的树。顶点编号为 11 到 NN，第 ii 条边连接顶点 AiA_i 和顶点 BiB_i。

请计算有多少对整数 (x,y)(x, y) 满足以下条件：

  • 0≤x≤N0 \leq x \leq N；
  • 可以从树中恰好选出 xx 个顶点，使得它们的度数之和恰好为 yy。

输入格式

输入以如下格式从标准输入读入：

NN A1A_1 B1B_1 A2A_2 B2B_2 ⋮\vdots AN−1A_{N-1} BN−1B_{N-1}

输出格式

请输出满足条件的 (x,y)(x, y) 的对数。

输入输出样例

  • 输入#1

    3
1 2
2 3

    输出#1

    6

  • 输入#2

    5
1 2
2 3
2 4
4 5

    输出#2

    16

  • 输入#3

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

    输出#3

    65

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤Ai<Bi≤N1 \leq A_i < B_i \leq N
  • 输入的图保证为一棵树。

样例解释 1

满足条件的 (x,y)(x, y) 共有以下 66 种情况：

  • x=0,y=0x=0, y=0
  • x=1,y=1x=1, y=1
  • x=1,y=2x=1, y=2
  • x=2,y=2x=2, y=2
  • x=2,y=3x=2, y=3
  • x=3,y=4x=3, y=4

例如，选择顶点 11 和顶点 22 时，度数之和为 33，因此 x=2,y=3x=2, y=3 满足条件。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页