bzoj1767[Ceoi2009]harbingers 斜率优化dp

1767: [Ceoi2009]harbingers

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 421 Solved: 112
[Submit][Status][Discuss]

Description

给定一颗树，树中每个结点有一个邮递员，每个邮递员要沿着唯一的路径走向capital(1号结点)，每到一个城市他可以有两种选择： 1.继续走到下个城市 2.让这个城市的邮递员替他出发。每个邮递员出发需要一个准备时间W[I]，他们的速度是V[I]，表示走一公里需要多少分钟。现在要你求出每个城市的邮递员到capital的最少时间(不一定是他自己到capital，可以是别人帮他） N<=100000 3 ≤ N ≤ 100 000 0 ≤ Si≤ 10^9 1 ≤ Vi≤ 10^9 The length of each road will not exceed 10 000 For 20% of the tests, N ≤ 2 500 For 50% of the tests, each town will have at most 2 adjacent roads (i.e., the graph of roads will be a line)

Input

N 以下N-1行A,B,C三个数表示A,B之间有一条长为C的边。再N行每行两数Wi,Vi 输出有一行N-1个数表示如题所述。

Output

Sample Input

5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

Sample Output

206 321 542 328

HINT

比较裸的斜率优化
由于是一棵树，所以向儿子节点走的时候不能完全更改栈的信息（因为回到父亲节点的时候必须撤销儿子节点的操作）
为了节省时间，可以直接二分查找出需要修改的位置，记录当前栈的信息，修改后进入儿子，回来的时候复原即可
修改只修改一个位置并把栈顶重新设置为那个位置，否则会花费很多时间

这篇博客不错http://www.cnblogs.com/zj75211/p/8148736.html

 1 #include<bits/stdc++.h>
 2 #define N 100005
 3 #define ll long long
 4 using namespace std;
 5 ll dis[N],f[N];
 6 int n,tp,tot,s[N],hd[N],v[N],w[N];
 7 struct edge{int v,w,next;}e[N<<1];
 8 double g(int i,int j){
 9     return (double)(f[i]-f[j])/(double)(dis[i]-dis[j]);
10 }
11 void adde(int u,int v,int w){
12     e[++tot].v=v;
13     e[tot].w=w;
14     e[tot].next=hd[u];
15     hd[u]=tot;
16 }
17 int find(int l,int r,int x){
18     int mid=0;
19     while(l<=r){
20         mid=(l+r)>>1;
21         if(g(s[mid+1],s[mid])<v[x])l=mid+1;
22         else if(g(s[mid],s[mid-1])>v[x])r=mid-1;
23         else return mid;
24     }
25     return mid;
26 }
27 int insert(int l,int r,int u){
28     int mid=0;
29     while(l<=r){
30         mid=(l+r)>>1;
31         if(g(s[mid+1],s[mid])<g(u,s[mid]))l=mid+1;
32         else if(g(s[mid],s[mid-1])>g(s[mid],u))r=mid-1;
33         else return mid;
34     }
35     return mid;
36 }
37 void dfs(int u,int fa){
38     int pos=find(1,tp,u);
39     f[u]=f[s[pos]]+w[u]+v[u]*(dis[u]-dis[s[pos]]);
40     pos=insert(1,tp,u)+1;
41     int siz=tp,tmp=s[pos];
42     s[pos]=u;tp=pos;
43     for(int i=hd[u];i;i=e[i].next){
44         int v=e[i].v;
45         if(v==fa)continue;
46         dis[v]=dis[u]+e[i].w;
47         dfs(v,u);
48     }
49     s[pos]=tmp;tp=siz;
50 }
51  
52 int main(){
53     scanf("%d",&n);
54     for(int i=1;i<n;i++){
55         int u,v,w;
56         scanf("%d%d%d",&u,&v,&w);
57         adde(u,v,w);adde(v,u,w);
58     }
59     for(int i=2;i<=n;i++)
60     scanf("%d%d",&w[i],&v[i]);
61     dfs(1,0);
62     for(int i=2;i<=n;i++){
63         printf("%lld",f[i]);
64         if(i!=n)putchar(' ');   
65     }
66     return 0;
67 }