POJ 1741tree-點分治入門

學習了一下點分治，如果理解有誤還請不吝賜教。

為了快速求得樹上任意兩點之間距離滿足某種關系的點對數，我們需要用到這種算法。

點分治是樹上的一種分治算法，依靠樹和子樹之間的關系進行分治從而降低復雜度。

和其他樹上的算法有一些區別的是，點分治算法不是先處理局部信息，再將他們匯總得到整個樹的信息。點分治處理的問題一般不是樹整體的信息，而是樹上局部的關系，這就導致我們不能將它看作一個整體，而應該從一開始就處理，在從上往下處理的過程中不斷完善信息。在這種思想下我覺得能夠更好的理解這個算法。

例如：

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
Input
The input contains several test cases. The first line of each test case contains two integers n, k. (n<=10000) The following n-1 lines each contains three integers u,v,l, which means there is an edge between node u and v of length l.
The last test case is followed by two zeros.
Output
For each test case output the answer on a single line.
Sample Input
5 4
1 2 3
1 3 1
1 4 2
3 5 1
0 0
Sample Output
8

題目的大概意思就是說，想要找到樹上兩點之間距離小于k的點對數（路徑是有長度的）。我們如何使用點分治算法來解決這個問題呢？

為了找到合適的分治方法，我們引入一個概念叫做樹的重心。樹的重心指的是以該節點為根形成的最大子樹規模最小的節點。聽起來可能有點繞，其實還是挺符合直覺的。指的就是，一個樹有多個節點，每個節點都可以作為這個樹的根，而一旦根節點確定，就會有多個子樹，這些子樹中規模最大的一般是根節點下直接相連的某個子樹。所謂樹的重心，就是這個最大子樹規模最小的節點。比如：在這里插入圖片描述
在上面這個圖中，我們選擇i節點作為樹的重心，它的子樹中規模最大的是3，選擇其他的都會比3大。

知道什么是重心以后，我們來看如何求一個樹的重心。直接看代碼吧

void GetRoot(int x,int father)
{int v;SonNum[x]=1;//子樹節點的總個數MaxNum[x]=1;//最大子樹的節點個數for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; //Vis[v]是用來標記是否已經處理過該節點了，這個標記會在后面修改，如果已經處理過我們就不要將這個節點再考慮進來了if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}MaxNum[x]=max(MaxNum[x],ss-SonNum[x]);if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x];
}

得到樹的重心以后我們就要對他進行處理，首先當然是統計子樹上任意一點到樹根（也就是樹的重心）的距離

void GetDis(int x,int father,int dis)
{int v;//Dis數組記錄樹上其他點到重心的距離，因為我們不需要知道哪個點，所以直接保存就可以Dis[++dlen]=dis;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,dis+Edge[i].len);}
}

得到距離以后我們就可以根據題目的要求進行計數啦。這里要求的是任意兩點的距離小于k，那我們就要先得到兩點間的距離。在以重心為根的樹上，在兩個不同子樹上的點的距離就是他們距離重心的距離和。可是如果在同一個子樹上的話就不是這樣了。但是我們不好確定兩個節點是否在同一個子樹上，所以先囫圇吞棗將同一個子樹上的都計算上，然后再訪問子樹將他們減去。

int Count(int x,int dis)
{for(int i=0;i<=dlen;++i) Dis[i]=0;dlen=0;GetDis(x,0,dis);sort(Dis+1,Dis+1+dlen);int l=1,r=dlen,ret=0;//如果l到r的距離小于k，則l到l和r之間的任意一點的距離都小于k，所以直接加上r-lwhile(l<=r){if(Dis[l]+Dis[r]<=kk) ret+=r-l,l++;else r--;}return ret;
}

但是顯然這樣是多算的，我們要減去在同一個子樹上的滿足條件的節點，他們會在更后面再次加上。

void Solve(int x)
{int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;//在這里減去同一個子樹的上錯誤加上的點ans-=Count(v,Edge[i].len);ss=SonNum[v]; rootx=INT_MAX; root=0;//處理子樹，再加上正確的點GetRoot(v,x);Solve(root);}
}

可能稍微有些難以理解的是為什么這樣就可以減去剛開始錯誤地加上的同一個子樹上的點。這里稍微解釋一下：

在這里插入圖片描述

還是以這個圖為例，假如我們一開始處理的是樹的重心i節點，那么我們正確計算的就是分布在四個子樹上之間的距離，錯誤計算的就是同一個子樹之間的距離，例如：D-A-i-A-E和E-A-i-A等，為了處理這個問題，我們后面又訪問了一下子節點，注意上面的Solve函數中的ans-=Count(v,Edge[i].len);，為什么這樣寫就可以減去子節點的影響呢？需要注意我們已經將重心的Vis[x]的值已經修改，因此子節點無法訪問除了當前子樹外的其他子樹，而且有一個初值Edge[i].len，這樣處理以后他們的Dis數組的值和之前從重心訪問是相同的。也就是說，之前會計入答案的，這里也會再次記入答案，且只計入了同一個子樹中的。減去他們以后就是正確的數目。

然后我們再訪問子樹。將子樹看作一個單獨的樹，再次同樣的處理。

AC代碼：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<cmath>using namespace std;const int MAXN=1e5+5;
struct edge
{int to,len,last;
}Edge[MAXN<<1]; int Last[MAXN],tot;
int n,kk,SonNum[MAXN],MaxNum[MAXN],Vis[MAXN],Dis[MAXN];
int ans,root,rootx,dlen,ss;int getint()
{int x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0'; c=getchar();}return x*sign;
}void Init()
{for(int i=0;i<=n;++i) Last[i]=0; tot=0; ans=0; for(int i=0;i<=n;++i) Vis[i]=false;
}void AddEdge(int u,int v,int w)
{Edge[++tot].to=v; Edge[tot].len=w; Edge[tot].last=Last[u]; Last[u]=tot;
}void Read()
{int u,v,w;for(int i=1;i<n;i++){u=getint(); v=getint(); w=getint();AddEdge(u,v,w); AddEdge(v,u,w);}
}void GetRoot(int x,int father)
{int v;SonNum[x]=1; MaxNum[x]=1;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}MaxNum[x]=max(MaxNum[x],ss-SonNum[x]);if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x];
}void GetDis(int x,int father,int dis)
{int v;Dis[++dlen]=dis;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,dis+Edge[i].len);}
}int Count(int x,int dis)
{for(int i=0;i<=dlen;++i) Dis[i]=0;dlen=0;GetDis(x,0,dis);sort(Dis+1,Dis+1+dlen);int l=1,r=dlen,ret=0;while(l<=r){if(Dis[l]+Dis[r]<=kk) ret+=r-l,l++;else r--;}return ret;
}void Solve(int x)
{int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;ans-=Count(v,Edge[i].len);ss=SonNum[v]; rootx=INT_MAX; root=0;GetRoot(v,x);Solve(root);}
}void Work()
{rootx=INT_MAX; ss=n; root=0;GetRoot(1,0); Solve(root);
}void Write()
{printf("%d\n",ans); 
}int main()
{while(1){Init();n=getint(); kk=getint();if(n==0 && kk==0) break;Read();Work();Write();}return 0;
}

參考博客：傳送門

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

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

相關文章

基于單鏈表的生產者消費者問題

基于單鏈表的生產者消費者問題

『生產者與消費者問題分析』「原理」生產者生產產品&#xff0c;消費者消費產品。產品如果被消費者消費完了&#xff0c;同時生產者又沒有生產出產品&#xff0c;消費者 就必須等待。同樣的&#xff0c;如果生產者生產了產品&#xff0c;而消費者沒有去消費&#x…
閱讀更多...
C++智能指針（一）智能指針的簡單介紹

C++智能指針（一）智能指針的簡單介紹

https://blog.csdn.net/nou_camp/article/details/70176949C智能指針 在正式了解智能指針前先看一下下面的一段代碼 #include<iostream> using namespace std; class A { public:A():_ptr(NULL), _a(0){}~A(){} public:int* _ptr;int _a; };void test() {A a;int *p1 ne…
閱讀更多...
聰聰可可-點分治

聰聰可可-點分治

聰聰和可可是兄弟倆&#xff0c;他們倆經常為了一些瑣事打起來&#xff0c;例如家中只剩下最后一根冰棍而兩人都想吃、兩個人都想玩兒電腦&#xff08;可是他們家只有一臺電腦&#xff09;……遇到這種問題&#xff0c;一般情況下石頭剪刀布就好了&#xff0c;可是他們已經玩兒…
閱讀更多...
C++智能指針（二）模擬實現三種智能指針

C++智能指針（二）模擬實現三種智能指針

https://blog.csdn.net/nou_camp/article/details/70186721在上一篇博客中提到了Auto_ptr(C智能指針&#xff08;一&#xff09;)&#xff0c;下面進行模擬實現Auto_ptr 采用類模板實現 #include<iostream> using namespace std; template<class T> class Autoptr …
閱讀更多...
Prime Distance On Tree-樹分治+FFT

Prime Distance On Tree-樹分治+FFT

題目描述 Problem description. You are given a tree. If we select 2 distinct nodes uniformly at random, what’s the probability that the distance between these 2 nodes is a prime number? Input The first line contains a number N: the number of nodes in this…
閱讀更多...
C++智能指針（三）總結

C++智能指針（三）總結

https://blog.csdn.net/nou_camp/article/details/70195795 在上一篇博客中&#xff08;C智能指針&#xff08;二&#xff09;&#xff09;模擬實現了三種智能指針。 其中最好的就是shared_ptr,但是這并不代表它就是最完美的&#xff0c;它也有問題&#xff0c;這個問題就是循環…
閱讀更多...
POJ2114-Boatherds-樹分治

POJ2114-Boatherds-樹分治

題目描述 Boatherds Inc. is a sailing company operating in the country of Trabantustan and offering boat trips on Trabantian rivers. All the rivers originate somewhere in the mountains and on their way down to the lowlands they gradually join and finally th…
閱讀更多...
c++11 你需要知道這些就夠了

c++11 你需要知道這些就夠了

https://blog.csdn.net/tangliguantou/article/details/50549751c11新特性舉著火把尋找電燈今天我就權當拋磚引玉&#xff0c;如有不解大家一起探討。有部分內容是引用自互聯網上的內容&#xff0c;如有問題請聯系我。T&& 右值引用 std::move 右值引用出現之前我們只能…
閱讀更多...
HDU5977-Garden of Eden-樹分治+FWT

HDU5977-Garden of Eden-樹分治+FWT

題目描述 When God made the first man, he put him on a beautiful garden, the Garden of Eden. Here Adam lived with all animals. God gave Adam eternal life. But Adam was lonely in the garden, so God made Eve. When Adam was asleep one night, God took a rib fro…
閱讀更多...
C++11新特性學習

C++11新特性學習

https://blog.csdn.net/tennysonsky/article/details/778170481、什么是C11C11標準為C編程語言的第三個官方標準&#xff0c;正式名叫ISO/IEC 14882:2011 - Information technology -- Programming languages -- C。在正式標準發布前&#xff0c;原名C0x。它將取代C標準第二版I…
閱讀更多...
C++ override 關鍵字用法

C++ override 關鍵字用法

override關鍵字作用&#xff1a; 如果派生類在虛函數聲明時使用了override描述符&#xff0c;那么該函數必須重載其基類中的同名函數&#xff0c;否則代碼將無法通過編譯。舉例子說明struct Base {virtual void Turing() 0;virtual void Dijkstra() 0;virtual void VNeumann…
閱讀更多...
Gym - 101981I-MagicPotion-最大流

Gym - 101981I-MagicPotion-最大流

題目描述 There are n heroes and m monsters living in an island. The monsters became very vicious these days, so the heroes decided to diminish the monsters in the island. However, the i-th hero can only kill one monster belonging to the set Mi. Joe, the st…
閱讀更多...
c++仿函數 functor

c++仿函數 functor

https://www.cnblogs.com/decade-dnbc66/p/5347088.html內容整理自國外C教材先考慮一個簡單的例子&#xff1a;假設有一個vector<string>&#xff0c;你的任務是統計長度小于5的string的個數&#xff0c;如果使用count_if函數的話&#xff0c;你的代碼可能長成這樣&#…
閱讀更多...
HDU4812-D Tree-樹分治

HDU4812-D Tree-樹分治

題目描述 There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a v…
閱讀更多...
成為C++高手之實戰項目

成為C++高手之實戰項目

https://blog.csdn.net/niu_gao/article/details/51458721 在內存中模擬出一副牌&#xff0c;然后模擬洗牌&#xff0c;發牌等動作。 流程是這樣的&#xff1a;構建一副牌保存到一個數組中—洗牌—創建玩家—向玩家發牌–輸出每個玩家的牌。 #include <stdio.h> #include…
閱讀更多...
C++中String類的實現

C++中String類的實現

https://www.cnblogs.com/zhizhan/p/4876093.html原文&#xff1a;http://noalgo.info/382.html String是C中的重要類型&#xff0c;程序員在C面試中經常會遇到關于String的細節問題&#xff0c;甚至要求當場實現這個類。只是由于時間關系&#xff0c;可能只要求實現構造函數、…
閱讀更多...
Ubuntu軟件更新失敗

Ubuntu軟件更新失敗

剛安裝好Ubuntu以后需要將系統的軟件都更新一下&#xff0c;但是遇到一個問題就是下載倉庫信息失敗&#xff0c;大概是這個樣子的錯誤&#xff1a; 經國遇到這樣的問題可以試一下下面這個命令&#xff1a; sudo rm -rf /var/lib/apt/lists/* sudo apt-get update參考網址&…
閱讀更多...
getsockname函數與getpeername函數的使用

getsockname函數與getpeername函數的使用

https://www.tuicool.com/articles/V3Aveygetsockname和getpeername函數 getsockname函數用于獲取與某個套接字關聯的本地協議地址 getpeername函數用于獲取與某個套接字關聯的外地協議地址 定義如下&#xff1a;[cpp] view plaincopy#include<sys/socket.h> int gets…
閱讀更多...
Ubuntu根目錄空間不足

Ubuntu根目錄空間不足

自己在固態硬盤上安裝的Ubuntu&#xff0c;結果只用了一天就顯示磁盤空間不足。查看空間以后發現Ubuntu自己安裝的時候默認給根目錄分配的是10GB,然而我們下載的軟件以及環境等一般都安裝在根目錄空間下&#xff0c;尤其是/usr目錄所占的空間很大。 不得已我在網上查找了如何給…
閱讀更多...
Linux命令【一】基本命令

Linux命令【一】基本命令

shell命令和bash命令相同&#xff0c;指的是命令解析器 快捷鍵 history 所有的歷史命令ctrl P 向上滾動命令 ctrl N 向下滾動命令 ctrlB將光標向前移動 ctrlF將光標向后移動 ctrlA移動到命令行頭部 ctrlE移動到命令行尾部 光標刪除操作&#xff1a;刪除光標前面字符ctrlh或…
閱讀更多...
最新文章

Copyright @ 2022~2023