count-subtrees-with-max-distance-between-cities

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There are <code>n</code> cities numbered from <code>1</code> to <code>n</code>. You are given an array <code>edges</code> of size <code>n-1</code>, where <code>edges[i] = [ui, vi]</code> represents a bidirectional edge between cities <code>ui</code> and <code>vi</code>. There exists a unique path between each pair of cities. In other words, the cities form a tree.

A subtree is a subset of cities where every city is reachable from every other city in the subset, where the path between each pair passes through only the cities from the subset. Two subtrees are different if there is a city in one subtree that is not present in the other.

For each <code>d</code> from <code>1</code> to <code>n-1</code>, find the number of subtrees in which the maximum distance between any two cities in the subtree is equal to <code>d</code>.

Return an array of size <code>n-1</code> where the <code>dth</code> element (1-indexed) is the number of subtrees in which the maximum distance between any two cities is equal to <code>d</code>.

Notice&nbsp;that&nbsp;the distance between the two cities is the number of edges in the path between them.

&nbsp;
Example 1:

<img alt="" src="https://assets.leetcode.com/uploads/2020/09/21/p1.png" style="width: 161px; height: 181px;" />

<pre>
Input: n = 4, edges = [[1,2],[2,3],[2,4]]
Output: [3,4,0]
Explanation:
The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.
The subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.
No subtree has two nodes where the max distance between them is 3.
</pre>

Example 2:

<pre>
Input: n = 2, edges = [[1,2]]
Output: [1]
</pre>

Example 3:

<pre>
Input: n = 3, edges = [[1,2],[2,3]]
Output: [2,1]
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 15</code></li>
	<li><code>edges.length == n-1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= ui, vi &lt;= n</code></li>
	<li>All pairs <code>(ui, vi)</code> are distinct.</li>
</ul>

countSubgraphsForEachDiameter

Count Subtrees With Max Distance Between Cities

Tree Diameter

tree-diameter

树的直径

Bit Manipulation

Tree

Dynamic Programming

Bitmask

Enumeration

给你 <code>n</code> 个城市，编号为从 <code>1</code> 到 <code>n</code> 。同时给你一个大小为 <code>n-1</code> 的数组 <code>edges</code> ，其中 <code>edges[i] = [ui, vi]</code> 表示城市 <code>ui</code> 和 <code>vi</code> 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵 树 。

一棵 子树 是城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。

对于 <code>d</code> 从 <code>1</code> 到 <code>n-1</code> ，请你找到城市间 最大距离 恰好为 <code>d</code> 的所有子树数目。

请你返回一个大小为 <code>n-1</code> 的数组，其中第 <code>d</code> 个元素（下标从 1 开始）是城市间 最大距离 恰好等于 <code>d</code> 的子树数目。

请注意，两个城市间距离定义为它们之间需要经过的边的数目。

 

示例 1：

<img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/11/p1.png" style="width: 161px; height: 181px;" />

<pre>
输入：n = 4, edges = [[1,2],[2,3],[2,4]]
输出：[3,4,0]
解释：
子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
不存在城市间最大距离为 3 的子树。
</pre>

示例 2：

<pre>
输入：n = 2, edges = [[1,2]]
输出：[1]
</pre>

示例 3：

<pre>
输入：n = 3, edges = [[1,2],[2,3]]
输出：[2,1]
</pre>

 

提示：

<ul>
	<li><code>2 <= n <= 15</code></li>
	<li><code>edges.length == n-1</code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 <= ui, vi <= n</code></li>
	<li>题目保证 <code>(ui, vi)</code> 所表示的边互不相同。</li>
</ul>