C++樹(二)【直徑,中心】

目錄:

樹的直徑:

樹的直徑的性質:?

性質1:直徑的端點一定是葉子節點????????????????

性質2:任意點的最長鏈端點一定是直徑端點。

性質3:如果一棵樹有多條直徑,那么它們必然相交,且有極長連續段(可以是一個點,交點為樹的中心)

性質4:樹T1的直徑為x,y,樹T2的直徑為s,t。現有一邊u,v與兩顆樹相連,新樹的直徑端點一點是x,y,s,t中的兩個

樹的直徑求解方法:

樹的直徑的端點

樹的中心

樹的中心求解:

樹的中心兩個性質:

????????證明:

公共點公共邊的求法:

總結:

一、樹的直徑的四個基礎性質

二、樹的直徑相關求解問題


樹的直徑:

定義:樹的直徑是樹上兩點間距離的最大值。即樹中最遠的兩個節點之間的距離被稱為樹的直徑,連接這兩點的路徑被稱為樹的最長鏈。

鏈1) 5- 7 - 8 -3

鏈2) 1- 4 - 7 - 8 - 3

直徑為17

樹的直徑的性質:?

性質1:直徑的端點一定是葉子節點????????????????
? ? ? ? 證明:假設直徑s-t外存在一點p相連->s-t-p st+tp>st<sp? ?不成立
性質2:任意點的最長鏈端點一定是直徑端點。
????????證明:

性質3:如果一棵樹有多條直徑,那么它們必然相交,且有極長連續段(可以是一個點,交點為樹的中心)
????????證明:

性質4:樹T1的直徑為x,y,樹T2的直徑為s,t。現有一邊u,v與兩顆樹相連,新樹的直徑端點一點是x,y,s,t中的兩個

證明:

?????????性質4分析:

uv連接后有兩種情況

1.新直徑不過uv,即現直徑為st或為xy。2.新直徑過uv,則現直徑為

max(vs,vt)+max(ux,uy)+uv。

這兩種情況都能保證新直徑端點為x,y,s,t中的任意兩個。新直徑為以上三個中最大值。

????????連邊uv求新樹直徑最小:
引理性質4可知:

st與xy不變,此時只能減下過uv的直徑大小。以max(vs,vt)為例,要使該值最小,則v應當在樹的中心位置,這樣vs與vt越均衡。

同理u也應該在T2的樹的中心位置。

????????連邊uv求新樹直徑最大:

與前面一致,以max(vs,vt)為例,要使得該值最大,則v應當選擇直徑端點位置。

因此uv選擇各自直徑的端點位置時,直徑最大。

樹的直徑求解方法:

引理性質2:任意點的最長鏈端點一定是直徑端點。

方法:隨意找一個點x,進行dfs找到最長鏈的端點s,再以端點s做第二遍dfs,此時可以找到直徑的第二個端點t。此時端點s到t的距離就是樹的直徑。

樹的直徑的端點

通過記錄父親節點的方式能夠把直徑上的所有點全部記錄下來。

在樹中,直徑端點是常用點(假設端點為s,t),我們樹上任意一點p所能到的最大距離,只有可能是到ps或pt

找到所有點到兩個直徑端點的距離方法

法一(樸素方法):

????????求出直徑端點后,以每個點為根做dfs,找到根節點到端點的距離。

????????復雜度O(N2)。

法二(優化方法):

????????第一次從任意點出發,必然能到達直徑的一個端點s。

????????第二次從s點進行dfs找到端點t,此時記錄所有點到s的距離。

????????第三次從t點進行dfs,記錄所有點到t的距離。

????????復雜度:O(n)

樹的中心

概念:以樹的中心為根時,從該根到每個葉子節點的最長路徑最短,使得路徑和平衡。

樹的中心求解:

????????我們現在已經知道求解任意一點到兩端點的距離,即根據性質2可很輕松得到每個點能到的最長路徑。求出每個點后的路徑后,一次遍歷便可知樹的中心點。

樹的中心兩個性質:

性質1:樹的中心一定在直徑上,且趨向于中點位置

性質2:樹的中心可以有一個(單中心),也可以有兩個(雙中心)

????????證明:

引理性質2,若樹的中心p不在直徑st上,st上有一點q與直徑聯通。中心點能到的最遠距離為:

max(qs,qt)+pq,若要使得該值最小,pq應當為0,因此p在直徑上。

同時為了讓max(qs,qt)更小,樹的中心要在直徑中點處。

直徑公共點證明與求解方法

以當一顆樹存在多條直徑時,引理性質3,公共邊一定連續,因此可以直接對公共點/邊進行求解

公共點公共邊的求法:

????????找到直徑左右端點s,t,從左往右遍歷直徑上的點進行

????????dfs,如果某點r在直徑外找到一點與到右端點t距離相同,點r右邊的點一定不是公共點。

????????同理,從右往左遍歷直徑上的點進行dfs,如果某點l在直徑外找到一點與到左端點s距離相同,l左邊的點一定不是公共點。此時,l->r就是我們直徑的公共點。

????????因此我們只需要找到公共點邊界l,r即可。使得l盡可能靠右,r盡可能靠左。

總結:

一、樹的直徑的四個基礎性質

性質1:直徑的端點一定是葉子節點

性質2:任意點的最長鏈端點一定是直徑端點

性質3:如果一棵樹有多條直徑,那么它們必然相交,且有極長連續段

性質4:兩顆樹加一條邊相連,構成的新樹直徑端點一點是x,y,s,t中的兩個

二、樹的直徑相關求解問題

1. 樹的直徑以及所有點到直徑左右端點距離的解法。

2. 樹的中心的含義以及求解方法。

3. 直徑的公共點/邊的求解方法。

4. 兩顆樹連邊后求新樹的最小/大直徑方法。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/45901.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/45901.shtml
英文地址,請注明出處:http://en.pswp.cn/web/45901.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

STM32中PC13引腳可以當做普通引腳使用嗎?如何配置STM32的TAMPER?

1.STM32中PC13引腳可以當做普通引腳使用嗎&#xff1f; 在STM32單片機中&#xff0c;PC13引腳可以作為普通IO使用&#xff0c;但需要進行一定的配置。PC13通常與RTC侵入檢測功能&#xff08;TAMPER&#xff09;復用&#xff0c;因此需要關閉TAMPER功能才能將其作為普通IO使用。…

服務端渲染框架:Nuxt.js 與 Next.js 的區別和對比

&#x1f49d;&#x1f49d;&#x1f49d;歡迎蒞臨我的博客&#xff0c;很高興能夠在這里和您見面&#xff01;希望您在這里可以感受到一份輕松愉快的氛圍&#xff0c;不僅可以獲得有趣的內容和知識&#xff0c;也可以暢所欲言、分享您的想法和見解。 推薦:「stormsha的主頁」…

2024國家護網面試小結

24年國護馬上就要開始&#xff0c;基本上大部分藍隊紅隊都已經準備入場了 今年護網第一年變成常態化護網&#xff0c;由十五天突然變成了兩個月常態化&#xff0c;導致今年護網有很多項目整的七零八落 博主今年參加了三家廠商藍隊護網面試&#xff0c;在這邊分享一下護網面試…

掌握這些技巧,讓你成為畫冊制作高手

在數字化的時代背景下&#xff0c;電子畫冊以其便捷的傳播方式、豐富的視覺表現形式&#xff0c;贏得了大眾的喜愛。它不僅能夠在個人電腦上展現&#xff0c;還能通過智能手機、平板電腦等多種移動設備隨時隨地被訪問和瀏覽。這種跨平臺的支持&#xff0c;使得無論你身處何地&a…

Html_Css問答集(12)

99、將上例的0%改為30%&#xff0c;會如何變化&#xff1f; none:延遲2秒間無色&#xff0c;3.8秒&#xff08;0%-30%占1.8秒&#xff09;前無色&#xff0c;之后變紅到5秒綠最后藍&#xff0c;動畫結束時恢復初始&#xff08;無色&#xff09;。 forward:延遲2秒間無色&am…

leetcode刷題總結——字符串匹配

KMP&#xff08;字符串匹配算法&#xff09; 主串或目標串&#xff1a;比較長的&#xff0c;我們就是在它里面尋找子串是否存在&#xff1b; 子串或模式串&#xff1a;比較短的。 前綴&#xff1a;字符串A和B&#xff0c;A BS&#xff0c;S非空&#xff0c;則B為A的前綴。 …

婚禮成本與籌備策略:一場夢幻婚禮的理性規劃

婚禮成本與籌備策略&#xff1a;一場夢幻婚禮的理性規劃 摘要 婚禮&#xff0c;作為人生中的重要儀式&#xff0c;承載著新人的愛情與夢想&#xff0c;同時也伴隨著不菲的經濟投入。本文旨在探討婚禮所需的大致成本、影響成本的主要因素以及婚禮籌備過程中的關鍵注意事項&…

【Java--數據結構】二叉樹

歡迎關注個人主頁&#xff1a;逸狼 創造不易&#xff0c;可以點點贊嗎~ 如有錯誤&#xff0c;歡迎指出~ 樹結構 樹是一種非線性的數據結構&#xff0c;它是由n&#xff08;n>0&#xff09;個有限結點組成一個具有層次關系的集合 注意&#xff1a;樹形結構中&#xff0c;子…

Transformer模型在多任務學習中的革新應用

在深度學習領域&#xff0c;多任務學習&#xff08;Multi-task Learning, MTL&#xff09;是一種訓練模型以同時執行多個任務的方法。這種方法可以提高模型的泛化能力&#xff0c;因為它允許模型在不同任務之間共享知識。近年來&#xff0c;Transformer模型因其在自然語言處理&…

【linux高級IO(三)】初識epoll

&#x1f493;博主CSDN主頁:杭電碼農-NEO&#x1f493; ? ?專欄分類:Linux從入門到精通? ? &#x1f69a;代碼倉庫:NEO的學習日記&#x1f69a; ? &#x1f339;關注我&#x1faf5;帶你學更多操作系統知識 ? &#x1f51d;&#x1f51d; Linux高級IO 1. 前言2. 初識e…

STM32 HRTIM生成PWM時遇到無法輸出PWM脈沖波形問題

在使用HRTIM生成PWM時&#xff0c;當把周期寄存器更新的設置放到while循環中時&#xff0c;無法輸出PWM脈沖波形&#xff0c;即使增加計數延時也無法輸出&#xff0c;最終只能放到中斷函數中執行后期寄存器值更新才能夠生成PWM脈沖波形。

主流大數據調度工具DolphinScheduler之數據ETL流程

今天給大家分享主流大數據調度工具DolphinScheduler&#xff0c;以及數據的ETL流程。 一&#xff1a;調度工具DS 主流大數據調度工具DolphinScheduler&#xff0c; 其定位&#xff1a;解決數據處理流程中錯綜復雜的依賴關系 任務支持類型&#xff1a;支持傳統的shell任務&a…

Python學習4---迭代器和生成器的區別

一、迭代器 定義&#xff1a;迭代器是一個可以記住遍歷的位置的對象。迭代器對象必須實現兩個方法&#xff0c;iter() 和 next()。字符串、列表或元組等數據類型都是可迭代對象&#xff0c;但它們不是迭代器&#xff0c;因為它們不具有 next() 方法。迭代器對象用于遍歷可迭代對…

冷卻塔由那些配件組成

1、淋水填料 將需要冷卻的水&#xff08;熱水&#xff09;多次濺灑成水滴或形成水膜&#xff0c;以增加水和空氣的接觸面積和時間&#xff0c;促進水和空氣的熱交換。 填料在開式橫流冷卻塔的作用是增加循環水與空氣的接觸面積&#xff0c;并延長冷卻水停留在空氣中的時間&am…

LabVIEW工業設備姿態監測系統

開發了一種基于LabVIEW的工業設備姿態監測系統&#xff0c;針對現有監測設備在適應性和反應時間上的不足&#xff0c;采用了LabVIEW軟件和STM32微控制器&#xff0c;通過高精度姿態傳感器實現了對設備姿態的快速準確監測&#xff0c;大大提高了工業作業的安全與效率。 項目背景…

C++深度解析教程筆記9-靜態成員變量,靜態成員函數,二階構造,友元,函數重載,操作符重載

C深度解析教程筆記9 第25課 - 類的靜態成員變量實驗-數對象個數&#xff08;失敗&#xff09;實驗-靜態變量小結 第26課 - 類的靜態成員函數實驗-修改對象的靜態變量數值實驗-利用靜態成員函數實驗-靜態變量靜態函數實現統計對象個數小結 第27課 - 二階構造模式實驗-初始化是否…

百度人臉識別Windows C++離線sdk C#接入

百度人臉識別Windows C離線sdk C#接入 目錄 說明 設計背景 ? 場景特點&#xff1a; ? 客戶特點&#xff1a; ? 核心需求&#xff1a; SDK 包結構 效果 代碼 說明 自己根據SDK封裝了動態庫&#xff0c;然后C#調用。 功能接口 設計背景 ? 場景特點&#xff1a; -…

【滲透入門】XSS

文章目錄 XSS漏洞XSS舉例XSS類型防御方式 XSS漏洞 XSS&#xff08;Cross-Site Scripting&#xff0c;跨站腳本攻擊&#xff09;是一種常見的Web應用程序安全漏洞。XSS漏洞發生在應用程序未能充分過濾用戶提供的數據&#xff0c;使得惡意腳本得以在不知情的用戶的瀏覽器中被執行…

ARFoundation系列講解 - 91 Immersal 簡介

一、Immersal 簡介 Immersal是一家專注于增強現實(AR)技術的公司,致力于開發和推廣空間感知解決方案(簡稱:大空間技術)。他們的核心產品是一個名為Immersal SDK的開發工具包,通過視覺定位(VPS)能夠輕松地在現實世界中實現高精度的定位和增強現實體驗。 二、Immersal …

Spring Boot集成Knife4j:實現高效API文檔管理

Spring Boot集成Knife4j&#xff1a;實現高效API文檔管理 在軟件開發過程中&#xff0c;編寫和維護接口文檔是一項必不可少的任務。隨著微服務架構的流行&#xff0c;API文檔的重要性日益凸顯。然而&#xff0c;傳統的手動編寫文檔方式不僅效率低下&#xff0c;而且容易出錯。…