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

 #include<bits/stdc++.h>
 #define N 100005
 #define ll long long
 using namespace std;
 ll dis[N],f[N];
 int n,tp,tot,s[N],hd[N],v[N],w[N];
 struct edge{int v,w,next;}e[N<<];
 double g(int i,int j){
     return (double)(f[i]-f[j])/(double)(dis[i]-dis[j]);
 }
 void adde(int u,int v,int w){
     e[++tot].v=v;
     e[tot].w=w;
     e[tot].next=hd[u];
     hd[u]=tot;
 }
 int find(int l,int r,int x){
     int mid=;
     while(l<=r){
         mid=(l+r)>>;
         if(g(s[mid+],s[mid])<v[x])l=mid+;
         else if(g(s[mid],s[mid-])>v[x])r=mid-;
         else return mid;
     }
     return mid;
 }
 int insert(int l,int r,int u){
     int mid=;
     while(l<=r){
         mid=(l+r)>>;
         if(g(s[mid+],s[mid])<g(u,s[mid]))l=mid+;
         else if(g(s[mid],s[mid-])>g(s[mid],u))r=mid-;
         else return mid;
     }
     return mid;
 }
 void dfs(int u,int fa){
     int pos=find(,tp,u);
     f[u]=f[s[pos]]+w[u]+v[u]*(dis[u]-dis[s[pos]]);
     pos=insert(,tp,u)+;
     int siz=tp,tmp=s[pos];
     s[pos]=u;tp=pos;
     for(int i=hd[u];i;i=e[i].next){
         int v=e[i].v;
         if(v==fa)continue;
         dis[v]=dis[u]+e[i].w;
         dfs(v,u);
     }
     s[pos]=tmp;tp=siz;
 }

 int main(){
     scanf("%d",&n);
     for(int i=;i<n;i++){
         int u,v,w;
         scanf("%d%d%d",&u,&v,&w);
         adde(u,v,w);adde(v,u,w);
     }
     for(int i=;i<=n;i++)
     scanf("%d%d",&w[i],&v[i]);
     dfs(,);
     for(int i=;i<=n;i++){
         printf("%lld",f[i]);
         if(i!=n)putchar(' ');
     }
     return ;
 }