lcpy gen -n 2285 # by problem numberlcpy gen -s maximum_total_importance_of_roads # by problem name
Problem
You are given an integer n denoting the number of cities in a country. The cities are numbered from 0 to n - 1.You are also given a 2D integer array roads where roads[i] = [a<sub>i</sub>, b<sub>i</sub>] denotes that there exists a bidirectional road connecting cities a<sub>i</sub> and b<sub>i</sub>.You need to assign each city with an integer value from 1 to n, where each value can only be used once. The importance of a road is then defined as the sum of the values of the two cities it connects.Return the maximum total importance of all roads possible after assigning the values optimally.
Examples
Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]Output: 43Explanation: The assigned values are [2,4,5,3,1].The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.
Input: n = 5, roads = [[0,3],[2,4],[1,3]]Output: 20Explanation: The assigned values are [4,3,2,5,1].The total importance of all roads is 9 + 3 + 8 = 20.
class Solution: # Time: O(E + V log V) where E = len(roads), V = n # Space: O(V) def maximum_importance(self, n: int, roads: list[list[int]]) -> int: degree = [0] * n for a, b in roads: degree[a] += 1 degree[b] += 1 degree.sort() return sum(d * (i + 1) for i, d in enumerate(degree))
{"docsConfig":{"theme":"mint","$schema":"https://www.mintlify.com/docs.json","name":"leetcode-py","description":"Modern Python LeetCode practice environment with automated problem generation, beautiful data structure visualizations, and comprehensive testing","colors":{"primary":"#3776AB","light":"#5A94C4","dark":"#387EB8"},"logo":{"light":"https://mintcdn.com/leetcode-py/aJKJ4BOUnXP-zM3G/img/brand/leetcode-py-lockup.svg?fit=max\u0026auto=format\u0026n=aJKJ4BOUnXP-zM3G\u0026q=85\u0026s=34c74a404ed256642a54345a92489c97","dark":"https://mintcdn.com/leetcode-py/aJKJ4BOUnXP-zM3G/img/brand/leetcode-py-lockup-dark.svg?fit=max\u0026auto=format\u0026n=aJKJ4BOUnXP-zM3G\u0026q=85\u0026s=263c5757fbf5e547de96291651e279e9"},"favicon":"https://mintcdn.com/leetcode-py/VCrzlUI648LnF7Pk/favicon.svg?fit=max\u0026auto=format\u0026n=VCrzlUI648LnF7Pk\u0026q=85\u0026s=3b1dffe162e80798a504a810fcbeba45","background":{"color":{"light":"#F8F9FB","dark":"#0D1117"}},"navbar":{"links":[{"href":"https://github.com/wislertt/leetcode-py","label":"GitHub"}]},"footer":{"socials":{"github":"https://github.com/wislertt/leetcode-py"},"links":[{"header":"Resources","items":[{"label":"PyPI","href":"https://pypi.org/project/leetcode-py-sdk"},{"label":"Why leetcode-py","href":"/getting-started/why-leetcode-py"},{"label":"Made by Wisaroot Lertthaweedech","href":"https://wisl.dev"}]}]},"seo":{"metatags":{"canonical":"https://leetcode-py.wisl.dev","og:image":"https://leetcode-py.wisl.dev/img/brand/og-card-light.png","twitter:card":"summary_large_image"},"organization":{"url":"https://leetcode-py.wisl.dev","sameAs":["https://github.com/wislertt/leetcode-py","https://pypi.org/project/leetcode-py-sdk/","https://wisl.dev"]},"indexing":"all"},"styling":{"codeblocks":{"theme":{"light":"github-light","dark":"github-dark"}},"latex":true},"metadata":{"timestamp":true},"markdown":{"instructions":["leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.","Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.","Examples are backed by tests; copy them verbatim."]},"navigation":{"pages":[]}},"deployment":{"deploymentMetadataValue":{"subdomain":"leetcode-py","hasAudioNarration":false,"actualSubdomain":"leetcode-py","customDomains":["leetcode-py.wisl.dev"],"gitSource":{"type":"github","owner":"wislertt","repo":"leetcode-py","deployBranch":"main","contentDirectory":"docs","isPrivate":true,"mountPath":"","label":""},"entitlements":{},"buildId":"6aeadd835fa1f5f231996c95","clientVersion":"0.0.4270","searchFilterCounts":[{"language":"default","tag":"Catalog","count":13},{"language":"default","tag":"Practice","count":5},{"language":"default","tag":"Troubleshooting","count":5},{"language":"default","tag":"Getting Started","count":3},{"language":"default","tag":"CLI","count":2},{"language":"default","tag":"Contributing","count":2},{"language":"default","tag":"Welcome","count":1}]},"assistantConfig":{"enableAskAiButton":false,"enableStarterQuestions":false,"enableContextualStarterQuestions":false,"enableAskAiSearchBar":true},"basePath":"","hasChatPermissions":false,"hasWebMcpPermissions":false,"toggles":[{"name":"kill-isr","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"custom-rbac-roles","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"agent-mintlify-slack","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"agent-integrations-settings","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"rbac-expansion","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"automations-pr-grouping","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"custom-prefix","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"analytics-v7","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"user-flows-analytics","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"no-publish-flow","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"workos-onboarding","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"snapshot-serving-live","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"stripTemperatureMiddleware","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"support-platform-pylon-zendesk","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"snapshot-serving","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"instant-rollback","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"granular-notifications-server","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"granular-notifications","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"automations-fable","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"fixed-ai-action-pricing","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"site-roles","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"automation-resolve-merge-conflict","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"scoped-publishing","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"mintql","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"page-level-analytics","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"editor-version-history-v2","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"billing-page-v2","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"full-page-search","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"workspace-projects","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"assistant-v5","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"fork-pr-previews","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"revalidation-jwt","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"workos-sso-scim","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"hobby-abuse-scan","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"dashboard-inbox","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"workos-signup","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"turbopuffer-dual-write","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"workos-enabled","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"approve-review-flow","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"editor-metadata","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"sso-setup-deadline-banner","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"turbopuffer-serve","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"live-agents","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"starter-pricing","enabled":true,"variant":{"name":"treatment","enabled":true,"payload":{"type":"string","value":"treatment"},"feature_enabled":true},"impressionData":false},{"name":"llms-txt-v2","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false},{"name":"wildcard-email-auth","enabled":true,"variant":{"name":"disabled","enabled":false,"feature_enabled":true},"impressionData":false}],"googleFontsInlined":false},"customCss":[{"filePath":"custom.css","content":".sd-catalog-table th:first-child,.sd-catalog-table td:first-child{min-width:0;width:3rem}html.dark .sd-hero-light{display:none}html:not(.dark) .sd-hero-dark{display:none}.sd-badges{display:flex;flex-wrap:wrap;gap:8px;align-items:center;justify-content:flex-start;margin:0 0 16px;padding:0}.sd-badges a,.sd-badges a:hover,.sd-badges a:visited{display:inline-flex;flex:0 0 auto;line-height:0;height:auto!important;max-height:24px;padding:0!important;margin:0!important;text-decoration:none!important;border-bottom:none!important;background:none!important;background-image:none!important}.sd-badges img{height:20px;width:auto;max-width:none;display:block;margin:0!important}.sd-preview{border:1px solid #387eb8;border-radius:10px}"}]}
{"page":{"pagePath":"problems/maximum-total-importance-of-roads","slug":"/problems/maximum-total-importance-of-roads","pageMetadata":{"title":"Maximum Total Importance of Roads","description":"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.","href":"/problems/maximum-total-importance-of-roads"},"description":{"compiledSource":"\"use strict\";\nconst {jsx: _jsx} = arguments[0];\nconst {useMDXComponents: _provideComponents} = arguments[0];\nfunction _createMdxContent(props) {\n const _components = {\n p: \"p\",\n ..._provideComponents(),\n ...props.components\n };\n return _jsx(_components.p, {\n children: \"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.\"\n });\n}\nfunction MDXContent(props = {}) {\n const {wrapper: MDXLayout} = {\n ..._provideComponents(),\n ...props.components\n };\n return MDXLayout ? _jsx(MDXLayout, {\n ...props,\n children: _jsx(_createMdxContent, {\n ...props\n })\n }) : _createMdxContent(props);\n}\nreturn {\n default: MDXContent\n};\n","frontmatter":{},"scope":{}},"pageType":"default","mdx":{"mdxSource":{"compiledSource":"\"use strict\";const{Fragment:_Fragment,jsx:_jsx,jsxs:_jsxs}=arguments[0];const{useMDXComponents:_provideComponents}=arguments[0];function _createMdxContent(props){const _components={a:`a`,code:`code`,em:`em`,img:`img`,li:`li`,p:`p`,pre:`pre`,span:`span`,strong:`strong`,tbody:`tbody`,td:`td`,th:`th`,thead:`thead`,tr:`tr`,ul:`ul`,..._provideComponents(),...props.components},{CodeBlock,Heading,Table}=_components;if(!CodeBlock)_missingMdxReference(`CodeBlock`,true);if(!Heading)_missingMdxReference(`Heading`,true);if(!Table)_missingMdxReference(`Table`,true);return _jsxs(_Fragment,{children:[_jsxs(_components.p,{children:[`LeetCode 2285, `,_jsx(_components.a,{href:`/catalog/medium`,children:`Medium`}),`. Topics: `,_jsx(_components.a,{href:`/catalog/topics/greedy`,children:`Greedy`}),`, `,_jsx(_components.a,{href:`/catalog/topics/graph-theory`,children:`Graph Theory`}),`, `,_jsx(_components.a,{href:`/catalog/topics/sorting`,children:`Sorting`}),`, `,_jsx(_components.a,{href:`/catalog/topics/heap-priority-queue`,children:`Heap (Priority Queue)`}),`. `,_jsx(_components.a,{href:`https://leetcode.com/problems/maximum-total-importance-of-roads/description/`,children:`View on LeetCode`}),`.`]}),`\n`,_jsxs(_components.p,{children:[`Generate this problem as a practice environment: tested reference solution, 19 `,_jsx(_components.a,{href:`/practice/testing`,children:`parametrized pytest cases`}),`, and a playground notebook:`]}),`\n`,_jsx(CodeBlock,{filename:``,numberOfLines:`2`,language:`shellscript`,children:_jsx(_components.pre,{className:`shiki shiki-themes github-light github-dark`,style:{backgroundColor:`#fff`,\"--shiki-dark-bg\":`#24292e`,color:`#24292e`,\"--shiki-dark\":`#e1e4e8`},language:`shellscript`,children:_jsxs(_components.code,{language:`shellscript`,numberOfLines:`2`,children:[_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#6F42C1`,\"--shiki-dark\":`#B392F0`},children:`lcpy`}),_jsx(_components.span,{style:{color:`#032F62`,\"--shiki-dark\":`#9ECBFF`},children:` gen`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` -n`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` 2285`}),_jsx(_components.span,{style:{color:`#6A737D`,\"--shiki-dark\":`#6A737D`},children:` # by problem number`})]}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#6F42C1`,\"--shiki-dark\":`#B392F0`},children:`lcpy`}),_jsx(_components.span,{style:{color:`#032F62`,\"--shiki-dark\":`#9ECBFF`},children:` gen`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` -s`}),_jsx(_components.span,{style:{color:`#032F62`,\"--shiki-dark\":`#9ECBFF`},children:` maximum_total_importance_of_roads`}),_jsx(_components.span,{style:{color:`#6A737D`,\"--shiki-dark\":`#6A737D`},children:` # by problem name`})]}),`\n`]})})}),`\n`,_jsx(Heading,{level:`2`,id:`problem`,children:`Problem`}),`\n`,_jsxs(_components.p,{children:[`You are given an integer `,_jsx(_components.code,{children:`n`}),` denoting the number of cities in a country. The cities are numbered from `,_jsx(_components.code,{children:`0`}),` to `,_jsx(_components.code,{children:`n - 1`}),`.`]}),`\n`,_jsxs(_components.p,{children:[`You are also given a 2D integer array `,_jsx(_components.code,{children:`roads`}),` where `,_jsx(_components.code,{children:`roads[i] = [a\u003csub>i\u003c/sub>, b\u003csub>i\u003c/sub>]`}),` denotes that there exists a `,_jsx(_components.strong,{children:`bidirectional`}),` road connecting cities `,_jsx(_components.code,{children:`a\u003csub>i\u003c/sub>`}),` and `,_jsx(_components.code,{children:`b\u003csub>i\u003c/sub>`}),`.`]}),`\n`,_jsxs(_components.p,{children:[`You need to assign each city with an integer value from `,_jsx(_components.code,{children:`1`}),` to `,_jsx(_components.code,{children:`n`}),`, where each value can only be used `,_jsx(_components.strong,{children:`once`}),`. The `,_jsx(_components.strong,{children:`importance`}),` of a road is then defined as the `,_jsx(_components.strong,{children:`sum`}),` of the values of the two cities it connects.`]}),`\n`,_jsxs(_components.p,{children:[`Return `,_jsxs(_components.em,{children:[`the `,_jsx(_components.strong,{children:`maximum total importance`}),` of all roads possible after assigning the values optimally.`]})]}),`\n`,_jsx(Heading,{level:`3`,id:`examples`,children:`Examples`}),`\n`,_jsx(_components.p,{children:_jsx(_components.img,{src:`https://assets.leetcode.com/uploads/2022/04/07/ex1drawio.png`,alt:`Example 1`})}),`\n`,_jsx(CodeBlock,{numberOfLines:`5`,language:`text`,children:_jsx(_components.pre,{className:`shiki shiki-themes github-light github-dark`,style:{backgroundColor:`#fff`,\"--shiki-dark-bg\":`#24292e`,color:`#24292e`,\"--shiki-dark\":`#e1e4e8`},language:`text`,children:_jsxs(_components.code,{language:`text`,numberOfLines:`5`,children:[_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`Input: n = 5, roads = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`Output: 43`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`Explanation: The assigned values are [2,4,5,3,1].`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`The total importance of all roads is 6 + 9 + 8 + 7 + 7 + 6 = 43.`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{})})]})})}),`\n`,_jsx(_components.p,{children:_jsx(_components.img,{src:`https://assets.leetcode.com/uploads/2022/04/07/ex2drawio.png`,alt:`Example 2`})}),`\n`,_jsx(CodeBlock,{numberOfLines:`5`,language:`text`,children:_jsx(_components.pre,{className:`shiki shiki-themes github-light github-dark`,style:{backgroundColor:`#fff`,\"--shiki-dark-bg\":`#24292e`,color:`#24292e`,\"--shiki-dark\":`#e1e4e8`},language:`text`,children:_jsxs(_components.code,{language:`text`,numberOfLines:`5`,children:[_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`Input: n = 5, roads = [[0,3],[2,4],[1,3]]`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`Output: 20`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`Explanation: The assigned values are [4,3,2,5,1].`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{children:`The total importance of all roads is 9 + 3 + 8 = 20.`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{})})]})})}),`\n`,_jsx(Heading,{level:`3`,id:`constraints`,children:`Constraints`}),`\n`,_jsxs(_components.ul,{children:[`\n`,_jsx(_components.li,{children:`2 \u003c= n \u003c= 5 * 10\u003csup>4\u003c/sup>`}),`\n`,_jsx(_components.li,{children:`1 \u003c= roads.length \u003c= 5 * 10\u003csup>4\u003c/sup>`}),`\n`,_jsx(_components.li,{children:`roads[i].length == 2`}),`\n`,_jsx(_components.li,{children:`0 \u003c= a\u003csub>i\u003c/sub>, b\u003csub>i\u003c/sub> \u003c= n - 1`}),`\n`,_jsx(_components.li,{children:`a\u003csub>i\u003c/sub> != b\u003csub>i\u003c/sub>`}),`\n`,_jsx(_components.li,{children:`There are no duplicate roads.`}),`\n`]}),`\n`,_jsx(Heading,{level:`2`,id:`solution`,children:`Solution`}),`\n`,_jsxs(_components.p,{children:[`Reference implementation from `,_jsx(_components.a,{href:`https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_total_importance_of_roads/solution.py`,children:`solution.py on GitHub`}),`, full suite in `,_jsx(_components.a,{href:`https://github.com/wislertt/leetcode-py/blob/main/leetcode/maximum_total_importance_of_roads/test_solution.py`,children:`test_solution.py`}),`:`]}),`\n`,_jsx(CodeBlock,{filename:``,numberOfLines:`10`,language:`python`,children:_jsx(_components.pre,{className:`shiki shiki-themes github-light github-dark`,style:{backgroundColor:`#fff`,\"--shiki-dark-bg\":`#24292e`,color:`#24292e`,\"--shiki-dark\":`#e1e4e8`},language:`python`,children:_jsxs(_components.code,{language:`python`,numberOfLines:`10`,children:[_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`class`}),_jsx(_components.span,{style:{color:`#6F42C1`,\"--shiki-dark\":`#B392F0`},children:` Solution`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`:`})]}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{style:{color:`#6A737D`,\"--shiki-dark\":`#6A737D`},children:` # Time: O(E + V log V) where E = len(roads), V = n`})}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{style:{color:`#6A737D`,\"--shiki-dark\":`#6A737D`},children:` # Space: O(V)`})}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:` def`}),_jsx(_components.span,{style:{color:`#6F42C1`,\"--shiki-dark\":`#B392F0`},children:` maximum_importance`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`(self, n: `}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:`int`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`, roads: list[list[`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:`int`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`]]) -> `}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:`int`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`:`})]}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` degree `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`=`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` [`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:`0`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`] `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`*`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` n`})]}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:` for`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` a, b `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`in`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` roads:`})]}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` degree[a] `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`+=`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` 1`})]}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` degree[b] `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`+=`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` 1`})]}),`\n`,_jsx(_components.span,{className:`line`,children:_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` degree.sort()`})}),`\n`,_jsxs(_components.span,{className:`line`,children:[_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:` return`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` sum`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`(d `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`*`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` (i `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`+`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` 1`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`) `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`for`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:` i, d `}),_jsx(_components.span,{style:{color:`#D73A49`,\"--shiki-dark\":`#F97583`},children:`in`}),_jsx(_components.span,{style:{color:`#005CC5`,\"--shiki-dark\":`#79B8FF`},children:` enumerate`}),_jsx(_components.span,{style:{color:`#24292E`,\"--shiki-dark\":`#E1E4E8`},children:`(degree))`})]}),`\n`]})})}),`\n`,_jsx(Heading,{level:`2`,id:`complexity`,children:`Complexity`}),`\n`,_jsxs(Table,{children:[_jsx(_components.thead,{children:_jsxs(_components.tr,{children:[_jsx(_components.th,{children:`Time`}),_jsx(_components.th,{children:`Space`})]})}),_jsx(_components.tbody,{children:_jsxs(_components.tr,{children:[_jsx(_components.td,{children:`O(E + V log V) where E = len(roads), V = n`}),_jsx(_components.td,{children:`O(V)`})]})})]}),`\n`,_jsx(Heading,{level:`2`,id:`tags`,children:`Tags`}),`\n`,_jsxs(_components.p,{children:[_jsx(_components.a,{href:`/catalog/neetcode`,children:`NeetCode All`}),`.`]})]})}function MDXContent(props={}){const{wrapper:MDXLayout}={..._provideComponents(),...props.components};return MDXLayout?_jsx(MDXLayout,{...props,children:_jsx(_createMdxContent,{...props})}):_createMdxContent(props)}return{default:MDXContent};function _missingMdxReference(id,component){throw new Error(`Expected `+(component?`component`:`object`)+\" `\"+id+\"` to be defined: you likely forgot to import, pass, or provide it.\")}","frontmatter":{},"scope":{"codeStyling":{"theme":{"light":"github-light","dark":"github-dark"}},"config":{},"pageMetadata":{"title":"Maximum Total Importance of Roads","description":"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.","href":"/problems/maximum-total-importance-of-roads"}}},"mdxSourceWithNoJs":null},"mdxExtracts":{"tableOfContents":[{"title":"Problem","slug":"problem","depth":2,"children":[{"title":"Examples","slug":"examples","depth":3,"children":[]},{"title":"Constraints","slug":"constraints","depth":3,"children":[]}]},{"title":"Solution","slug":"solution","depth":2,"children":[]},{"title":"Complexity","slug":"complexity","depth":2,"children":[]},{"title":"Tags","slug":"tags","depth":2,"children":[]}],"codeExamples":{}},"jsLinks":[],"subdomain":"leetcode-py","siteName":"leetcode-py","title":"Maximum Total Importance of Roads - leetcode-py","navMaps":{"firstHrefInVersion":{},"firstHrefInLanguage":{}},"lastModified":"2026-09-07T03:04:54.562Z","gitLastModified":"2026-09-07T03:04:07.000Z","originalFileLocation":"problems/maximum-total-importance-of-roads.mdx"},"headHtml":"\u003cscript data-mint-head>(function(){var d=document.documentElement,p=null;if(!p){try{p=localStorage.getItem(\"isDarkMode\")}catch(e){}if(p==='true')p='dark';else if(p==='false')p='light';if(p!=='light'\u0026\u0026p!=='dark'\u0026\u0026p!=='system')p=\"system\"}var r=p==='system'?(matchMedia(\"(prefers-color-scheme: dark)\").matches?'dark':'light'):p;d.classList.remove(r==='dark'?'light':'dark');d.classList.add(r);d.setAttribute(\"data-theme-preference\",p)})();\u003c/script>\u003cmeta data-mint-head name=\"description\" content=\"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.\">\u003cmeta data-mint-head name=\"application-name\" content=\"leetcode-py\">\u003cmeta data-mint-head name=\"generator\" content=\"Mintlify\">\u003clink data-mint-head rel=\"icon\" type=\"image/png\" sizes=\"192x192\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon/android-chrome-192x192.png\" media=\"(prefers-color-scheme: light)\">\u003clink data-mint-head rel=\"apple-touch-icon\" type=\"image/png\" sizes=\"180x180\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon/apple-touch-icon.png\">\u003clink data-mint-head rel=\"icon\" type=\"image/png\" sizes=\"16x16\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon/favicon-16x16.png\" media=\"(prefers-color-scheme: light)\">\u003clink data-mint-head rel=\"icon\" type=\"image/png\" sizes=\"32x32\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon/favicon-32x32.png\" media=\"(prefers-color-scheme: light)\">\u003clink data-mint-head rel=\"shortcut icon\" type=\"image/x-icon\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon/favicon.ico\" media=\"(prefers-color-scheme: light)\">\u003clink data-mint-head rel=\"icon\" type=\"image/png\" sizes=\"192x192\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon-dark/android-chrome-192x192.png\" media=\"(prefers-color-scheme: dark)\">\u003clink data-mint-head rel=\"icon\" type=\"image/png\" sizes=\"16x16\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon-dark/favicon-16x16.png\" media=\"(prefers-color-scheme: dark)\">\u003clink data-mint-head rel=\"icon\" type=\"image/png\" sizes=\"32x32\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon-dark/favicon-32x32.png\" media=\"(prefers-color-scheme: dark)\">\u003clink data-mint-head rel=\"shortcut icon\" type=\"image/x-icon\" href=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon-dark/favicon.ico\" media=\"(prefers-color-scheme: dark)\">\u003cmeta data-mint-head property=\"og:title\" content=\"Maximum Total Importance of Roads - leetcode-py\">\u003cmeta data-mint-head property=\"og:description\" content=\"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.\">\u003cmeta data-mint-head property=\"og:site_name\" content=\"leetcode-py\">\u003cmeta data-mint-head property=\"og:url\" content=\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads\">\u003cmeta data-mint-head property=\"og:type\" content=\"website\">\u003cmeta data-mint-head property=\"og:image\" content=\"https://leetcode-py.wisl.dev/img/brand/og-card-light.png\">\u003cmeta data-mint-head property=\"og:image:width\" content=\"1200\">\u003cmeta data-mint-head property=\"og:image:height\" content=\"630\">\u003cmeta data-mint-head name=\"twitter:card\" content=\"summary_large_image\">\u003cmeta data-mint-head name=\"twitter:title\" content=\"Maximum Total Importance of Roads - leetcode-py\">\u003cmeta data-mint-head name=\"twitter:description\" content=\"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.\">\u003cmeta data-mint-head name=\"twitter:image\" content=\"https://leetcode-py.wisl.dev/img/brand/og-card-light.png\">\u003cmeta data-mint-head name=\"twitter:image:width\" content=\"1200\">\u003cmeta data-mint-head name=\"twitter:image:height\" content=\"630\">\u003cmeta data-mint-head name=\"msapplication-config\" content=\"/mintlify-assets/_mintlify/favicons/leetcode-py/MPF4VdYq1xxotsp3/_generated/favicon/browserconfig.xml\">\u003cmeta data-mint-head name=\"apple-mobile-web-app-title\" content=\"leetcode-py\">\u003cmeta data-mint-head name=\"msapplication-TileColor\" content=\"#3776AB\">\u003clink data-mint-head rel=\"canonical\" href=\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads\">\u003clink data-mint-head rel=\"alternate\" type=\"application/xml\" href=\"/sitemap.xml\">\u003clink data-mint-head rel=\"alternate\" type=\"text/markdown\" href=\"/problems/maximum-total-importance-of-roads.md\">\u003cscript data-mint-head type=\"application/ld+json\">{\"@context\":\"https://schema.org\",\"@graph\":[{\"@type\":\"Organization\",\"@id\":\"https://leetcode-py.wisl.dev/#organization\",\"name\":\"leetcode-py\",\"url\":\"https://leetcode-py.wisl.dev\",\"logo\":{\"@type\":\"ImageObject\",\"url\":\"https://mintcdn.com/leetcode-py/aJKJ4BOUnXP-zM3G/img/brand/leetcode-py-lockup.svg?fit=max\u0026auto=format\u0026n=aJKJ4BOUnXP-zM3G\u0026q=85\u0026s=34c74a404ed256642a54345a92489c97\"},\"sameAs\":[\"https://github.com/wislertt/leetcode-py\",\"https://pypi.org/project/leetcode-py-sdk/\",\"https://wisl.dev\"]},{\"@type\":\"WebSite\",\"@id\":\"https://leetcode-py.wisl.dev#website\",\"name\":\"leetcode-py\",\"url\":\"https://leetcode-py.wisl.dev\",\"publisher\":{\"@id\":\"https://leetcode-py.wisl.dev/#organization\"}},{\"@type\":\"WebPage\",\"@id\":\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads#webpage\",\"url\":\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads\",\"name\":\"Maximum Total Importance of Roads\",\"description\":\"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.\",\"dateModified\":\"2026-09-07T03:04:07.000Z\",\"isPartOf\":{\"@id\":\"https://leetcode-py.wisl.dev#website\"}},{\"@type\":[\"Article\",\"TechArticle\"],\"@id\":\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads#article\",\"headline\":\"Maximum Total Importance of Roads\",\"name\":\"Maximum Total Importance of Roads\",\"description\":\"Tested Python solution for LeetCode 2285 with 19 pytest cases. Generate a practice environment with lcpy.\",\"url\":\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads\",\"mainEntityOfPage\":{\"@id\":\"https://leetcode-py.wisl.dev/problems/maximum-total-importance-of-roads#webpage\"},\"image\":\"https://leetcode-py.wisl.dev/img/brand/og-card-light.png\",\"dateModified\":\"2026-09-07T03:04:07.000Z\",\"publisher\":{\"@id\":\"https://leetcode-py.wisl.dev/#organization\"},\"isPartOf\":{\"@id\":\"https://leetcode-py.wisl.dev#website\"}}]}\u003c/script>\u003cscript data-mint-head type=\"application/ld+json\">{\"@context\":\"https://schema.org\",\"@type\":\"WebSite\",\"name\":\"leetcode-py\",\"publisher\":{\"@type\":\"Organization\",\"name\":\"leetcode-py\"},\"provider\":{\"@type\":\"Organization\",\"name\":\"Mintlify\",\"url\":\"https://mintlify.com\"}}\u003c/script>","agentPointerHref":"/problems/maximum-total-importance-of-roads.md","siteName":"leetcode-py","nav":{"global":null,"groups":[{"group":"Welcome","pages":[{"title":"LeetCode Practice Environments in Python","sidebarTitle":"leetcode-py","href":"/index"}]},{"group":"Getting Started","pages":[{"title":"Install the lcpy CLI via pip or uv","sidebarTitle":"Installation","href":"/getting-started/installation"},{"title":"lcpy Quickstart: First Problem in 5 Commands","sidebarTitle":"Quickstart","href":"/getting-started/quickstart"},{"title":"LeetCode Practice Environment vs a Bare Editor","sidebarTitle":"Why leetcode-py","href":"/getting-started/why-leetcode-py"}]},{"group":"Practice","pages":[{"title":"Anatomy of a problem","href":"/practice/problem-anatomy"},{"title":"Test LeetCode Solutions Locally with pytest","sidebarTitle":"Test locally","href":"/practice/test-locally"},{"title":"LeetCode Python Test Cases with pytest","sidebarTitle":"Testing","href":"/practice/testing"},{"title":"Visualizations","href":"/practice/visualizations"},{"title":"Notebooks","href":"/practice/notebooks"}]},{"group":"CLI","pages":[{"title":"lcpy CLI: Generate and List Problems","sidebarTitle":"lcpy","href":"/cli/lcpy"},{"title":"Blind 75, Grind 75, NeetCode and Others","sidebarTitle":"Collections","href":"/cli/collections"}]},{"group":"Catalog","pages":[{"title":"LeetCode Problem Catalog: All Collections","sidebarTitle":"Catalog","href":"/catalog/index"},{"title":"All LeetCode Problems in Python with Tests","sidebarTitle":"All Problems","href":"/catalog/all"},{"title":"Easy LeetCode Problems in Python with Tests","sidebarTitle":"Easy","href":"/catalog/easy"},{"title":"Medium LeetCode Problems in Python with Tests","sidebarTitle":"Medium","href":"/catalog/medium"},{"title":"Hard LeetCode Problems in Python with Tests","sidebarTitle":"Hard","href":"/catalog/hard"},{"title":"Topics","href":"/catalog/topics"},{"title":"Grind 75 in Python with Tested Solutions","sidebarTitle":"Grind 75","href":"/catalog/grind-75"},{"title":"Grind Collection in Python: Tested Solutions","sidebarTitle":"Grind","href":"/catalog/grind"},{"title":"Blind 75 in Python with Tested Solutions","sidebarTitle":"Blind 75","href":"/catalog/blind-75"},{"title":"NeetCode 150 in Python with Tested Solutions","sidebarTitle":"NeetCode 150","href":"/catalog/neetcode-150"},{"title":"NeetCode 250 in Python with Tested Solutions","sidebarTitle":"NeetCode 250","href":"/catalog/neetcode-250"},{"title":"NeetCode All in Python with Tested Solutions","sidebarTitle":"NeetCode All","href":"/catalog/neetcode"},{"title":"AlgoMaster 75 in Python with Tested Solutions","sidebarTitle":"AlgoMaster 75","href":"/catalog/algo-master-75"}]},{"group":"Contributing","pages":[{"title":"Add a New LeetCode Problem End to End","sidebarTitle":"Problem creation","href":"/contributing/problem-creation"},{"title":"Contributor Reference: bakefile Tasks","sidebarTitle":"bakefile","href":"/contributing/bakefile"}]},{"group":"Troubleshooting","pages":[{"title":"lcpy Errors and Troubleshooting","sidebarTitle":"Troubleshooting","href":"/troubleshooting/index"},{"title":"lcpy gen Error: Problem Not Found","sidebarTitle":"Problem not found","href":"/troubleshooting/unknown-problem"},{"title":"lcpy gen Error: Problem Already Exists","sidebarTitle":"Already exists","href":"/troubleshooting/files-already-exist"},{"title":"Visualizations Show ASCII Instead of Diagrams","sidebarTitle":"ASCII diagrams","href":"/troubleshooting/graphviz-missing"},{"title":"Playground Notebook Cells Do Not Render","sidebarTitle":"Notebook cells","href":"/troubleshooting/notebook-cells"}]}]},"basePath":"","title":"Maximum Total Importance of Roads - leetcode-py","deploymentId":"dpl_DyXGnKeCjZyA3sUdfMJ7FjkdBefg","buildId":"dpl_DyXGnKeCjZyA3sUdfMJ7FjkdBefg","dynamics":["a74be98ba7"],"chunks":["zoom-image-lightbox-BQ4tbj_9.js","lightbox-handle-r17bVUz3.js"]}