#P16087. [Oni2018]tricolor

    ID: 15298 传统题 1600ms 256MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2200提高树形 DP树上背包子树合并剪除无效容量

[Oni2018]tricolor

题目描述

Tanaka 有一棵包含 NN 个节点的树,节点编号为 1∼N1\sim N。他希望把每个节点染成白色或黑色,使“兄弟节点对”的数量最大。

两个不同节点称为一对兄弟,当且仅当:

  • 它们都被染成白色;并且
  • 它们之间的简单路径满足以下条件之一:
    • 两点直接由一条边相连;
    • 路径上的中间节点全部为黑色。

换句话说,两白点之间如果直接相邻,或中间只隔着黑点,就会贡献一对。

任务

给定一棵树,求通过给节点染黑/白能够得到的最大兄弟节点对数量。

输入格式

第一行包含一个正整数 TT,表示测试组数。

接下来给出 TT 组测试。每组测试:

第一行一个整数 NN。

接下来 N−1N-1 行,每行两个整数 x,yx,y,表示树中的一条边。

输出格式

包含 TT 行,第 ii 行输出第 ii 组测试的答案。

数据范围与限制

  • 1≤T≤101\le T\le 10
  • 1≤N≤50001\le N\le 5000
  • 每条边满足 1≤x,y≤N1\le x,y\le N,且 x≠yx\ne y

子任务:

  • 5 分:T=1T=1 且 N≤15N\le 15
  • 10 分:T=1T=1 且 N≤20N\le 20
  • 5 分:所有树恰有 2 个叶子,且 N≤500N\le 500
  • 10 分:所有树中所有叶子只连到某条链两端的两个节点上,且 N≤500N\le 500
  • 50 分:N≤500N\le 500
  • 20 分:无额外限制

样例

输入

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

输出

7
1

样例解释

第一棵树中,最优染色可以得到 7 对兄弟节点。第二棵树只有两个相邻节点,把二者都染成白色即可得到 1 对。