題目描述
給出一個N個點的帶權樹(N <= 50000)。每個點到任意葉子節點的最長距離記為Di。詢問M < 300 次，對每次詢問，找到長度最大的區間[l,r]，使得Di(l<=i<=r)的最大值和最小值的差不超過Q。
吐槽
1.因為一個很細小的錯誤查了一下午，最后寫了一個naive程序對拍給拍出來了....
2.這個題就是把兩個不相干的問題拼接到一起了... 無節操...
算法分析
首先要求所有的Di，如果對每個點為起點搜索時間復雜度為O(n^2)，TLE....
這里用到很強大的樹形DP: 設點a為根(我的程序里點a就是點0)，搜索一次求出以a為根每個點i到葉子節點的最大距離i.first。
和到葉子節點且與最長路徑的邊集沒有交集的次長路徑的距離i.second。
求出這個之后就可以DP了: 對于點v，我們需要求出v到所有葉子節點的最長路v.first1和與最長路沒有交集的次長路v.second1。
假設v唯一的父親u已經求好了。那么有兩種情況：
1. u的最長路不可能經過v (u.first1 > distance(u,v) + v.first)
這樣的話v.first1肯定等于u.first1 + distance(u,v)
那么v的所有子孫也肯定和v的情況是一樣的，于是我們不需要計算v.second1。
2. u的最長路可能經過v (u.first1 = distance(u,v) + v.first)
這樣的話v.first1有兩種可能
第一種可能是v.first1 = v.first
第二種可能是v.first1 = u.second1 + distance(u,v)
對于第一種情況v.second1 = max(v.second , u.second1 + distance(u,v))
對于第二種情況v.second1 也不需要計算了....
對于那個根a，a.first1 = a.first， a.second1 = a.second
Di求好了，那么對于查詢怎么辦呢？
不難想到可以二分枚舉區間長度，然后回來驗證最小的差值是否大于Q (因為這個值是隨著區間長度單調變化的)
驗證的話可以用RMQ，但是RMQ可以處理任意長度區間的最值查詢。這里對于每一次枚舉區間長度是不變的，殺雞焉用牛刀？
那么對于固定區間的最值查詢可以使用單調隊列，這里就不介紹了，不熟悉的同學可以參考
傻崽的博客 其實這樣查詢會超時(常數微大)，不過把每次枚舉的結果存一下就不會超時了 OTL... DP思想隨處見啊...
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
西月弦 閱讀(453)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告