题目描述
给出一个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
西月弦 阅读(444)
评论(0) 编辑 收藏 引用 所属分类:
解题报告