題目描述
給出一個(gè)N個(gè)點(diǎn)的帶權(quán)樹(shù)(N <= 50000)。每個(gè)點(diǎn)到任意葉子節(jié)點(diǎn)的最長(zhǎng)距離記為Di。詢(xún)問(wèn)M < 300 次，對(duì)每次詢(xún)問(wèn)，找到長(zhǎng)度最大的區(qū)間[l,r]，使得Di(l<=i<=r)的最大值和最小值的差不超過(guò)Q。
吐槽
1.因?yàn)橐粋€(gè)很細(xì)小的錯(cuò)誤查了一下午，最后寫(xiě)了一個(gè)naive程序?qū)ε慕o拍出來(lái)了....
2.這個(gè)題就是把兩個(gè)不相干的問(wèn)題拼接到一起了... 無(wú)節(jié)操...
算法分析
首先要求所有的Di，如果對(duì)每個(gè)點(diǎn)為起點(diǎn)搜索時(shí)間復(fù)雜度為O(n^2)，TLE....
這里用到很強(qiáng)大的樹(shù)形DP: 設(shè)點(diǎn)a為根(我的程序里點(diǎn)a就是點(diǎn)0)，搜索一次求出以a為根每個(gè)點(diǎn)i到葉子節(jié)點(diǎn)的最大距離i.first。
和到葉子節(jié)點(diǎn)且與最長(zhǎng)路徑的邊集沒(méi)有交集的次長(zhǎng)路徑的距離i.second。
求出這個(gè)之后就可以DP了: 對(duì)于點(diǎn)v，我們需要求出v到所有葉子節(jié)點(diǎn)的最長(zhǎng)路v.first1和與最長(zhǎng)路沒(méi)有交集的次長(zhǎng)路v.second1。
假設(shè)v唯一的父親u已經(jīng)求好了。那么有兩種情況：
1. u的最長(zhǎng)路不可能經(jīng)過(guò)v (u.first1 > distance(u,v) + v.first)
這樣的話(huà)v.first1肯定等于u.first1 + distance(u,v)
那么v的所有子孫也肯定和v的情況是一樣的，于是我們不需要計(jì)算v.second1。
2. u的最長(zhǎng)路可能經(jīng)過(guò)v (u.first1 = distance(u,v) + v.first)
這樣的話(huà)v.first1有兩種可能
第一種可能是v.first1 = v.first
第二種可能是v.first1 = u.second1 + distance(u,v)
對(duì)于第一種情況v.second1 = max(v.second , u.second1 + distance(u,v))
對(duì)于第二種情況v.second1 也不需要計(jì)算了....
對(duì)于那個(gè)根a，a.first1 = a.first， a.second1 = a.second
Di求好了，那么對(duì)于查詢(xún)?cè)趺崔k呢？
不難想到可以二分枚舉區(qū)間長(zhǎng)度，然后回來(lái)驗(yàn)證最小的差值是否大于Q (因?yàn)檫@個(gè)值是隨著區(qū)間長(zhǎng)度單調(diào)變化的)
驗(yàn)證的話(huà)可以用RMQ，但是RMQ可以處理任意長(zhǎng)度區(qū)間的最值查詢(xún)。這里對(duì)于每一次枚舉區(qū)間長(zhǎng)度是不變的，殺雞焉用牛刀？
那么對(duì)于固定區(qū)間的最值查詢(xún)可以使用單調(diào)隊(duì)列，這里就不介紹了，不熟悉的同學(xué)可以參考
傻崽的博客 其實(shí)這樣查詢(xún)會(huì)超時(shí)(常數(shù)微大)，不過(guò)把每次枚舉的結(jié)果存一下就不會(huì)超時(shí)了 OTL... DP思想隨處見(jiàn)啊...
1 #include<iostream>
2 #include<cstdio>
3 #include<cstdlib>
4 #include<cassert>
5 using namespace std;
6 #define re(i,n) for(int i = 0; i<n ; i++)
7 #define debug1
8 const int V = 50005;
9 const int E = V*2;
10 const int inf = ~0u>>2;
11 int e,head[V],nxt[E],pnt[E],cost[E];
12 typedef long long ll;
13 ll dp[V][2];
14 template <typename T> inline void chkmax(T &a,const T b) {if( a < b) a = b;}
15 template <typename T> inline void chkmin(T &a,const T b) {if( a > b) a = b;}
16 void dfsa(int u,int f = 0){
17 dp[u][0] = dp[u][1] = 0;
18 for(int i = head[u] ; i!=-1 ; i= nxt[i]){
19 int v = pnt[i];
20 if(v != f){
21 dfsa(v,u);
22 if(dp[v][0]+ cost[i] > dp[u][0]){
23 dp[u][1] = dp[u][0];
24 dp[u][0] = dp[v][0]+cost[i];
25 }
26 else chkmax(dp[u][1],dp[v][0] + cost[i]);
27 }
28 }
29 }
30 void dfs(int u,int f =0,int c =0){
31 if(u) {
32 if(dp[f][0] - c == dp[u][0]){
33 if(dp[u][0]< c + dp[f][1]){
34 dp[u][1] = dp[u][0];
35 dp[u][0] = c + dp[f][1];
36 }
37 else {
38 chkmax(dp[u][1],dp[f][1] + c);
39 }
40 }
41 else dp[u][0] = dp[f][0] + c;
42 }
43 for(int i = head[u]; i!=-1 ; i=nxt[i]){
44 int v =pnt[i];
45 if(v != f){
46 dfs(v,u,cost[i]);
47 }
48 }
49 }
50 void add_edge(int u,int v,int c){
51 nxt[e] = head[u];
52 head[u] = e;
53 pnt[e] = v;
54 cost[e] = c;
55 e++;
56 }
57 int n,m;
58 int Q[V][2];
59 int Dp[V];
60 ll cal(int len){
61 if(Dp[len] != -1) return Dp[len];
62 int front=0,tail=0,front1=0,tail1=0;
63 ll ans = inf;
64 re(i,n) {
65 while(tail > front && dp[i][0] < dp[Q[tail-1][0]][0]) tail --;
66 Q[tail++][0] = i;
67 while(tail1 > front1 && dp[i][0] > dp[Q[tail1-1][1]][0]) tail1 --;
68 Q[tail1++][1] = i;
69 if(i - Q[front][0] >= len) front ++;
70 if(i - Q[front1][1] >= len) front1 ++;
71 assert(front < tail && front1 <tail1);
72 if(i >= len -1)
73 chkmin(ans,dp[Q[front1][1]][0] - dp[Q[front][0]][0]);
74 assert(ans >= 0);
75 // cout<<Q[front1][1]<<" "<<Q[front][0]<<endl;
76 }
77 // cout<<endl;
78 return Dp[len]=ans;
79 }
80 int main(){
81 while(~scanf("%d%d",&n,&m) && !(!n&&!m)){
82 int u,v,c;
83 e = 0;
84 re(i,n) head[i] =Dp[i]= -1;
85 Dp[n] = -1;
86 re(i,n-1){
87 scanf("%d%d%d",&u,&v,&c);
88 u--,v--;
89 add_edge(u,v,c);
90 add_edge(v,u,c);
91 }
92 if(n){
93 dfsa(0);
94 dfs(0);
95 }
96 #ifdef debug
97 re(i,n) cout<<dp[i][0]<<" "; cout<<endl;
98 return 0;
99 #endif
100 while(m--){
101 int x;
102 scanf("%d",&x);
103 int l = 1, r = n+1;
104 while(l < r){
105 int mid = l+r >>1;
106 if(cal(mid) > x) r = mid;
107 else l = mid + 1;
108 }
109 printf("%d\n",l-1);
110 }
111 }
112 }
113
posted on 2012-04-26 16:42
西月弦 閱讀(460)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
解題報(bào)告