算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述

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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理