照例先貼題面（汪汪汪）

2500: 幸福的道路

Time Limit:?20 Sec??Memory Limit:?256 MB
Submit:?368??Solved:?145
[Submit][Status][Discuss]

Description

小T與小L終于決定走在一起,他們不想浪費在一起的每一分每一秒,所以他們決定每天早上一同晨練來享受在一起的時光. 他們畫出了晨練路線的草圖,眼尖的小T發現可以用樹來描繪這個草圖. 他們不愿枯燥的每天從同一個地方開始他們的鍛煉,所以他們準備給起點標號后順序地從每個起點開始(第一天從起點一開始,第二天從起點二開始……). 而且他們給每條道路定上一個幸福的值.很顯然他們每次出發都想走幸福值和最長的路線(即從起點到樹上的某一點路徑中最長的一條). 他們不愿再經歷之前的大起大落,所以決定連續幾天的幸福值波動不能超過M(即一段連續的區間并且區間的最大值最小值之差不超過M).他們想知道要是這樣的話他們最多能連續鍛煉多少天(hint:不一定從第一天一直開始連續鍛煉)? 現在，他們把這個艱巨的任務交給你了!

Input

第一行包含兩個整數N, M(M<=10^9). 第二至第N行,每行兩個數字Fi , Di, 第i行表示第i個節點的父親是Fi,且道路的幸福值是Di.

Output

最長的連續鍛煉天數

Sample Input

3 2
1 1
1 3

Sample Output

3
數據范圍：
50%的數據N<=1000
80%的數據N<=100 000
100%的數據N<=1000 000 對于這道題來說我們可以考慮預處理出每個結點的最長路徑長然后亂搞 對于預處理我在考場上寫了個對于每個結點DFS一遍求最長，然后$std::set$維護最大最小值，總時間復雜度瓶頸為預處理$O(n^2)$ 實際上我們可以先求這個樹的直徑結點，然后從分別從兩個直徑結點進行DFS并取最大值來預處理出最長路徑長。直徑為樹中最長的一條路徑。這一過程需要固定的4遍DFS所以時間復雜度$O(n)$ 考場上鬼使神差地腦抽認為求直徑會有反例 然后就是求最長連續區間的問題，我的策略是建立左右兩個哨兵，采用一直讓右哨兵前進并更新最大值直至最大最小值超過限制條件，超限之后采用不斷刪除左哨兵的值并前進直至符合條件的貪心策略。因為$std::set$的插入與查詢是$O(logn)$，每個點肯定要插入/刪除一次所以貪心過程時間復雜度$O(nlogn)$，總時間復雜度$O(nlogn)$ 這里其實還可以使用單調隊列，但是因為單調隊列要固定區間長度所以只能采取二分長度策略，總時間復雜度也是$O(nlogn)$。 然后袋馬時間： GitHub 1 #include <set> 2 #include <cstdio> 3 #include <algorithm> 4 5 const int MAXE=2000010; 6 const int MAXV=1000010; 7 8 struct Edge{ 9 int from; 10 int to; 11 int dis; 12 Edge* next; 13 }; 14 Edge E[MAXE]; 15 Edge* head[MAXV]; 16 Edge* top=E; 17 18 int n; 19 int m; 20 int lg1; 21 int lg2; 22 int dis[MAXV]; 23 24 void Initialize(); 25 std::pair<int,int> DFS(int,int,int); 26 void DFSA(int,int,int); 27 void Insert(int,int,int); 28 int Sweep(); 29 30 int main(){ 31 Initialize(); 32 lg1=DFS(1,0,0).second; 33 lg2=DFS(lg1,0,0).second; 34 DFSA(lg1,0,0); 35 DFSA(lg2,0,0); 36 printf("%d\n",Sweep()); 37 // printf("%d %d\n",lg1,lg2); 38 return 0; 39 } 40 41 std::pair<int,int> DFS(int root,int prt,int dis){ 42 std::pair<int,int> ans(dis,root); 43 for(Edge* i=head[root];i!=NULL;i=i->next){ 44 if(i->to==prt) 45 continue; 46 ans=std::max(ans,DFS(i->to,root,dis+i->dis)); 47 } 48 return ans; 49 } 50 51 void DFSA(int root,int prt,int dis){ 52 ::dis[root]=std::max(::dis[root],dis); 53 for(Edge* i=head[root];i!=NULL;i=i->next){ 54 if(i->to==prt) 55 continue; 56 DFSA(i->to,root,dis+i->dis); 57 } 58 } 59 60 int Sweep(){ 61 int l=1,r=1,ans=0; 62 // std::priority_queue<int,std::vector<int>,std::less<int>> qmax; 63 // std::priority_queue<int,std::vector<int>,std::greater<int>> qmin; 64 std::multiset<int> s; 65 while(r<=n){ 66 // printf("%d\n",r); 67 s.insert(dis[r]); 68 while(*(--s.end())-*s.begin()>m){ 69 s.erase(s.find(dis[l])); 70 ++l; 71 } 72 ans=std::max(ans,int(s.size())); 73 ++r; 74 } 75 return ans; 76 } 77 78 void Initialize(){ 79 int a,b; 80 scanf("%d%d",&n,&m); 81 for(int i=2;i<=n;i++){ 82 scanf("%d%d",&a,&b); 83 Insert(a,i,b); 84 Insert(i,a,b); 85 } 86 } 87 88 inline void Insert(int from,int to,int dis){ 89 top->to=to; 90 top->dis=dis; 91 top->from=from; 92 top->next=head[from]; 93 head[from]=top; 94 top++; 95 } Backup

以及圖包時間

?

轉載于:https://www.cnblogs.com/rvalue/p/7191518.html

總結

以上是生活随笔為你收集整理的[BZOJ 2500] 幸福的道路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。