{"id":7484,"date":"2020-10-11T13:08:05","date_gmt":"2020-10-11T20:08:05","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7484"},"modified":"2020-10-14T12:41:16","modified_gmt":"2020-10-14T19:41:16","slug":"leetcode-1617-count-subtrees-with-max-distance-between-cities","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1617-count-subtrees-with-max-distance-between-cities\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1617. Count Subtrees With Max Distance Between Cities"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1617. Count Subtrees With Max Distance Between Cities - \u5237\u9898\u627e\u5de5\u4f5c EP362\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/qag7m9VRf-A?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>There are&nbsp;<code>n<\/code>&nbsp;cities numbered from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>. You are given an array&nbsp;<code>edges<\/code>&nbsp;of size&nbsp;<code>n-1<\/code>, where&nbsp;<code>edges[i] = [u<sub>i<\/sub>, v<sub>i<\/sub>]<\/code>&nbsp;represents a bidirectional edge between cities&nbsp;<code>u<sub>i<\/sub><\/code>&nbsp;and&nbsp;<code>v<sub>i<\/sub><\/code>. There exists a unique path between each pair of cities. In other words, the cities form a&nbsp;<strong>tree<\/strong>.<\/p>\n\n\n\n<p>A&nbsp;<strong>subtree<\/strong>&nbsp;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.<\/p>\n\n\n\n<p>For each&nbsp;<code>d<\/code>&nbsp;from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n-1<\/code>, find the number of subtrees in which the&nbsp;<strong>maximum distance<\/strong>&nbsp;between any two cities in the subtree is equal to&nbsp;<code>d<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>an array of size<\/em>&nbsp;<code>n-1<\/code>&nbsp;<em>where the&nbsp;<\/em><code>d<sup>th<\/sup><\/code><em>element&nbsp;<strong>(1-indexed)<\/strong>&nbsp;is the number of subtrees in which the&nbsp;<strong>maximum distance<\/strong>&nbsp;between any two cities is equal to&nbsp;<\/em><code>d<\/code>.<\/p>\n\n\n\n<p><strong>Notice<\/strong>&nbsp;that&nbsp;the&nbsp;<strong>distance<\/strong>&nbsp;between the two cities is the number of edges in the path between them.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/09\/21\/p1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 4, edges = [[1,2],[2,3],[2,4]]\n<strong>Output:<\/strong> [3,4,0]\n<strong>Explanation:\n<\/strong>The subtrees with subsets {1,2}, {2,3} and {2,4} have a max distance of 1.\nThe subtrees with subsets {1,2,3}, {1,2,4}, {2,3,4} and {1,2,3,4} have a max distance of 2.\nNo subtree has two nodes where the max distance between them is 3.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 2, edges = [[1,2]]\n<strong>Output:<\/strong> [1]\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> n = 3, edges = [[1,2],[2,3]]\n<strong>Output:<\/strong> [2,1]\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><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;= u<sub>i<\/sub>, v<sub>i<\/sub>&nbsp;&lt;= n<\/code><\/li><li>All pairs&nbsp;<code>(u<sub>i<\/sub>, v<sub>i<\/sub>)<\/code>&nbsp;are distinct.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution1: Brute Force<\/strong> <strong>+ Diameter of tree<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362.png\" alt=\"\" class=\"wp-image-7500\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Try all subtrees and find the diameter of that subtree (longest distance between any node)<\/p>\n\n\n\n<p>Time complexity: O(2^n * n)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges, int last = -1) {\n    vector<vector<int>> g(n);\n    for (const auto& e : edges)\n      g[e[0] - 1].push_back(e[1] - 1), g[e[1] - 1].push_back(e[0] - 1);\n    \n    vector<int> seen(n, -1), seen2;\n    queue<int> q;\n    \n    auto bfs = [&](int start, vector<int>& seen) -> pair<int, int> {\n      q.push(start);\n      seen[start] = 1;\n      int count = 0, dist = -1;\n      while (!q.empty()) {\n        int s = q.size();        \n        while (s--) {\n          last = q.front(); q.pop();\n          ++count;\n          for (int v : g[last])\n            if (seen[v] != -1 && !seen[v]++) q.push(v);\n        }\n        ++dist;\n      }\n      return {dist, count};\n    };\n    \n    vector<int> ans(n - 1);\n    for (int s = 0; s < 1 << n; ++s) {\n      if (__builtin_popcount(s) <= 1) continue;\n      fill(begin(seen), end(seen), -1);\n      for (int i = 0; i < n; ++i) if (s &#038; (1 << i)) seen[i] = 0;\n      seen2 = seen;\n      const int start = 31 - __builtin_clz(s &#038; (s - 1));\n      if (bfs(start, seen).second != __builtin_popcount(s)) continue;      \n      ++ans[bfs(last, seen2).first - 1];\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: DP on Trees<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-2.png\" alt=\"\" class=\"wp-image-7501\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-3.png\" alt=\"\" class=\"wp-image-7502\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-4.png\" alt=\"\" class=\"wp-image-7503\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-5.png\" alt=\"\" class=\"wp-image-7504\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-5.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-5-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-5-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-6.png\" alt=\"\" class=\"wp-image-7505\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-6.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-6-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-6-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-7.png\" alt=\"\" class=\"wp-image-7506\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-7.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-7-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-7-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-8.png\" alt=\"\" class=\"wp-image-7507\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-8.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-8-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-8-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-9.png\" alt=\"\" class=\"wp-image-7508\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-9.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-9-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/10\/1617-ep362-9-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[i][k][d] := # of subtrees rooted at i with tree diameter of d and the distance from i to the farthest node is k.<\/p>\n\n\n\n<p>Time complexity: O(n^5)<br>Space complexity: O(n^3)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, 4ms, 8.8MB\nclass Solution {\npublic:\n  vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {    \n    vector<vector<int>> g(n);\n    for (const auto& e : edges) {\n      g[e[0] - 1].push_back(e[1] - 1);\n      g[e[1] - 1].push_back(e[0] - 1);\n    }\n    vector<vector<vector<int>>> dp(n);    \n    vector<int> sizes(n);\n    function<void(int, int)> dfs = [&](int u, int p) {\n      if (!dp[u].empty()) return;      \n      dp[u] = vector<vector<int>>(n, vector<int>(n));\n      dp[u][0][0] = 1;\n      sizes[u] = 1;\n      for (int v : g[u]) {\n        if (v == p) continue;\n        dfs(v, u);\n        vector<vector<int>> dpu(dp[u]);\n        for (int d1 = 0; d1 < sizes[u]; ++d1)\n          for (int k1 = 0; k1 <= d1; ++k1) {\n            if (!dp[u][k1][d1]) continue;\n            for (int d2 = 0; d2 < sizes[v]; ++d2)\n              for (int k2 = 0; k2 <= d2; ++k2) {\n                const int d = max({d1, d2, k1 + k2 + 1});\n                const int k = max(k1, k2 + 1);\n                dpu[k][d] += dp[u][k1][d1] * dp[v][k2][d2];\n              }\n          }\n        swap(dpu, dp[u]);\n        sizes[u] += sizes[v];\n      }\n    };\n    vector<int> ans(n - 1);\n    dfs(0, -1);\n    for (int i = 0; i < n; ++i) \n      for (int k = 0; k < n; ++k)\n        for (int d = 1; d < n; ++d)\n          ans[d - 1] += dp[i][k][d];\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There are&nbsp;n&nbsp;cities numbered from&nbsp;1&nbsp;to&nbsp;n. You are given an array&nbsp;edges&nbsp;of size&nbsp;n-1, where&nbsp;edges[i] = [ui, vi]&nbsp;represents a bidirectional edge between cities&nbsp;ui&nbsp;and&nbsp;vi. There exists a unique path between&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[660,77,217,566,28,661],"class_list":["post-7484","post","type-post","status-publish","format-standard","hentry","category-tree","tag-diameter","tag-graph","tag-hard","tag-longest-path","tag-tree","tag-tree-dp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7484","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7484"}],"version-history":[{"count":13,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7484\/revisions"}],"predecessor-version":[{"id":7512,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7484\/revisions\/7512"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7484"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7484"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7484"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}