【BZOJ 3672】 3672: [Noi2014]购票 （CDQ分治+点分治+斜率优化）**

3672: [Noi2014]购票

Description

 今年夏天，NOI在SZ市迎来了她30周岁的生日。来自全国 n 个城市的OIer们都会从各地出发，到SZ市参加这次盛会。
       全国的城市构成了一棵以SZ市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 n 个城市用 1 到 n 的整数编号。其中SZ市的编号为 1。对于除SZ市之外的任意一个城市 v，我们给出了它在这棵树上的父亲城市 fv  以及到父亲城市道路的长度 sv。
从城市 v 前往SZ市的方法为：选择城市 v 的一个祖先 a，支付购票的费用，乘坐交通工具到达 a。再选择城市 a 的一个祖先 b，支付费用并到达 b。以此类推，直至到达SZ市。
对于任意一个城市 v，我们会给出一个交通工具的距离限制 lv。对于城市 v 的祖先 a，只有当它们之间所有道路的总长度不超过 lv  时，从城市 v 才可以通过一次购票到达城市 a，否则不能通过一次购票到达。对于每个城市 v，我们还会给出两个非负整数 pv,qv  作为票价参数。若城市 v 到城市 a 所有道路的总长度为 d，那么从城市 v 到城市 a 购买的票价为 dpv+qv。
每个城市的OIer都希望自己到达SZ市时，用于购票的总资金最少。你的任务就是，告诉每个城市的OIer他们所花的最少资金是多少。

Input

第 1 行包含2个非负整数 n,t，分别表示城市的个数和数据类型（其意义将在后面提到）。输入文件的第 2 到 n 行，每行描述一个除SZ之外的城市。其中第 v 行包含 5 个非负整数 f_v,s_v,p_v,q_v,l_v，分别表示城市 v 的父亲城市，它到父亲城市道路的长度，票价的两个参数和距离限制。请注意：输入不包含编号为 1 的SZ市，第 2 行到第 n 行分别描述的是城市 2 到城市 n。

Output

输出包含 n-1 行，每行包含一个整数。其中第 v 行表示从城市 v+1 出发，到达SZ市最少的购票费用。同样请注意：输出不包含编号为 1 的SZ市。

Sample Input

7 3
1 2 20 0 3
1 5 10 100 5
2 4 10 10 10
2 9 1 100 10
3 5 20 100 10
4 4 20 0 10

Sample Output


40
150
70
149
300
150

HINT

对于所有测试数据，保证 0≤pv≤106，0≤qv≤1012，1≤fv<v；保证 0<sv≤lv≤2×1011，且任意城市到SZ市的总路程长度不超过 2×1011。


输入的 t 表示数据类型，0≤t<4，其中：


当 t=0 或 2 时，对输入的所有城市 v，都有 fv=v-1，即所有城市构成一个以SZ市为终点的链；


当 t=0 或 1 时，对输入的所有城市 v，都有 lv=2×1011，即没有移动的距离限制，每个城市都能到达它的所有祖先；


当 t=3 时，数据没有特殊性质。


n=2×10^5

Source

【分析】

　　一开始还以为很简单，以为凸包是可以随便加减的，就按着那棵树添加、减掉就好了。

　　说明我还是没有真正理解凸包啊。

　　还有一个我忽略的问题就是

　　

　　PO姐说的问题，最优解不在凸包上，但是经过l的分割后l左侧的点无法选择，最优解就进入了凸包，这种情况没法维护。。。。

　　所以这个斜率优化和我以前的有一点不一样，就是要二分查找。

　　然后我也说不清楚，看题解吧，这个说得比较好：

首先方程很好想..f[x]=min(f[x],f[y]+(Dist[x]−Dist[y])∗p[x]+q[x])y是x的祖先f[x]=min(f[x],f[y]+(Dist[x]−Dist[y])∗p[x]+q[x])y是x的祖先

这样也很容易想到斜率优化，主要的问题是，序列上的斜率优化利用的是单调队列，因为每个点只可能被插入删除一次，所以均摊复杂度是O(1)的。

但是树上的并不能达到这样...所以考虑如何维护这样的凸壳。

考虑树分治，不过和以往的树分治不同..有根树分治？ 有种类似CDQ分治的思想。

分治一棵以x为根的子树，切当前重心为root，首先对包含xx的子树进行分治，使得x−−root这段的dp值都得到更新。

然后考虑对剩下的子树中的点的影响，将剩下子树中的点全部提取出来，按照能到达的距离排序，然后按着这个顺序将root−−x的点插入并维护凸包，对于下面这些点，在凸包上二分更新答案。

这样就处理完了x−−root的路径上的dp对其余点的影响，然后对其余子树继续点分下去即可。

这样的复杂度是O(Nlog2N)的...

转自：http://www.cnblogs.com/DaD3zZ-Beyonder/p/6391404.html

听说有树剖的方法，是O(Nlog3N)O(Nlog3N)，不过我没看，表示不会，以后可以看看。

调代码调了很久，好心塞。。

我的维护的是一个左下凸包。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<iostream>
  5 #include<algorithm>
  6 using namespace std;
  7 #define Maxn 200010
  8 #define LL long long
  9 
 10 LL mymax(LL x,LL y) {return x>y?x:y;}
 11 LL mymin(LL x,LL y) {return x<y?x:y;}
 12 
 13 struct node
 14 {
 15     LL x,y,c,next;
 16     bool w;
 17 }t[Maxn];LL len=0;
 18 LL first[Maxn];
 19 
 20 void ins(LL x,LL y,LL c)
 21 {
 22     t[++len].x=x;t[len].y=y;t[len].c=c;
 23     t[len].next=first[x];first[x]=len;
 24     t[len].w=1;
 25 }
 26 
 27 LL p[Maxn],q[Maxn],lim[Maxn],dep[Maxn];
 28 LL ans[Maxn],fa[Maxn];
 29 
 30 LL sm[Maxn],mx[Maxn],rt;
 31 void dfs(LL x,LL tot)
 32 {
 33     sm[x]=mx[x]=1;
 34     for(LL i=first[x];i;i=t[i].next) if(t[i].w)
 35     {
 36         LL y=t[i].y;
 37         dep[y]=dep[x]+t[i].c;
 38         dfs(y,tot);
 39         sm[x]+=sm[y];
 40         mx[x]=mymax(mx[x],sm[y]);
 41     }
 42     mx[x]=mymax(mx[x],tot-sm[x]);
 43     if(rt==0||mx[x]<=mx[rt]) rt=x;
 44 }
 45 
 46 LL id[Maxn];
 47 LL f[Maxn];
 48 
 49 void dfs2(LL x)
 50 {
 51     id[++id[0]]=x;
 52     for(LL i=first[x];i;i=t[i].next) if(t[i].w)
 53     {
 54         dfs2(t[i].y);
 55     }
 56 }
 57 
 58 bool cmp(LL x,LL y) {return dep[x]-lim[x]>dep[y]-lim[y];}
 59 LL X(LL x) {return -dep[x];}
 60 LL Y(LL x) {return f[x];}
 61 
 62 bool bigger(LL x,LL y,LL z)
 63 {
 64     double k1=(Y(y)-Y(x))*1.0/(X(y)-X(x)),
 65            k2=(Y(z)-Y(y))*1.0/(X(z)-X(y));
 66     return k1>=k2;
 67 }
 68 
 69 LL Q[Maxn],ql;
 70 void add(LL x)
 71 {
 72     if(f[x]==f[0]) return;
 73     while(ql>=2&&bigger(Q[ql-1],Q[ql],x)) ql--;
 74     Q[++ql]=x;
 75 }
 76 
 77 LL mul(LL x,LL y)
 78 {
 79     LL A=x,B=y;
 80     A=A*B;
 81     return A;
 82 }
 83 
 84 void get_ans(LL x)
 85 {
 86     if(ql==0) return;
 87     LL l=1,r=ql;
 88     while(l<r)
 89     {
 90         LL mid=(l+r+1)>>1;
 91         LL M=Q[mid],N=Q[mid-1];
 92         if(-p[x]*1.0>=(Y(M)-Y(N))*1.0/(X(M)-X(N))) l=mid;
 93         else r=mid-1;
 94     }
 95     if(f[x]>mul(X(Q[l]),p[x])+Y(Q[l])+mul(p[x],dep[x])+q[x]) 
 96         f[x]=mul(X(Q[l]),p[x])+Y(Q[l])+mul(p[x],dep[x])+q[x];
 97     // f[x]=mymin(f[x],X(Q[l])*p[x]+Y(Q[l])+p[x]*dep[x]+q[x]);
 98 }
 99 
100 void ffind(LL x,LL tot)
101 {
102     if(tot==1) return;
103     rt=0;
104     // dep[x]=0;
105     dfs(x,tot);
106     for(LL i=first[rt];i;i=t[i].next) t[i].w=0;
107     LL nw=rt;
108     ffind(x,tot-sm[rt]+1);
109     
110     id[0]=0;
111     for(LL i=first[nw];i;i=t[i].next) dfs2(t[i].y);
112     sort(id+1,id+1+id[0],cmp);
113     
114     LL now=nw;ql=0;
115     for(LL i=1;i<=id[0];i++)
116     {
117         while(dep[now]>=dep[id[i]]-lim[id[i]])
118         {
119             add(now);
120             if(now==x) break;
121             now=fa[now];
122         }
123         get_ans(id[i]);
124         // printf("f[%d]=%d
",id[i],f[id[i]]);
125     }
126     
127     for(LL i=first[nw];i;i=t[i].next)
128     {
129         LL y=t[i].y;
130         ffind(y,sm[y]);
131     }
132 }
133 
134 int main()
135 {
136     LL n,t;
137     scanf("%lld%lld",&n,&t);
138     memset(first,0,sizeof(first));
139     memset(f,127,sizeof(f));f[1]=0;
140     fa[1]=0;
141     for(LL i=2;i<=n;i++)
142     {
143         LL l;
144         scanf("%lld%lld%lld%lld%lld",&fa[i],&l,&p[i],&q[i],&lim[i]);
145         ins(fa[i],i,l);
146     }
147     dep[1]=0;
148     ffind(1,n);
149     for(LL i=2;i<=n;i++)
150     {
151         if(f[i]==f[0]) printf("0
");
152         else 
153             printf("%lld
",f[i]);
154     }
155     return 0;
156 }
View Code

一气之下全部long long了。。

这是一道好题hhh

2017-02-15 13:35:50

 

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Konjakmoyu/p/6401046.html