[bzoj1767][Ceoi2009]harbingers (slope optimization on trees)


Given a tree, each node in the tree has a postman. Each postman should go to capital (node 1) along a unique path. There are two choices for each city: 1. Continue to the next city; 2. Let the postman in this city set out for him. Each postman needs a preparation time W[I], their speed is V[I], indicating how many minutes it takes to walk a kilometer. Now, you need to find out the minimum time for a postman to go to capital in each city (not necessarily to go to capital himself, but others can help him) 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 ≤ 2500 for 50% of the tests, each town will have at most 2 advanced roads (i.e., the Graph of roads will be a line)


Input
N-1 lines A,B and C below n represent A. there is an edge of C between B. Then n lines, each line has two numbers of WI, and the output of VI has one line, n-1 numbers, as described in the title.


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


solution:

Let dep [j] > dep [k], the current query point is i, if j is better than k,
There are f [J] + (DEP [i] - dep [J]) * V [i] + w [i] < f [k] + (DEP [i] - dep [J]) * V [i] + w [i]
Simplified to: F [J] - f [k] < (DEP [J] - dep [k]) * V [i]
Namely: (f [J] - f [k] / (DEP [J] - dep [k] < v [i]
The lower convex shell of monotone stack maintenance slope is enough.
Because it's a tree. When you pop up the stack, you don't really pop it up. Instead, you mark where it should be inserted, change only the value of this position, and change the top.
After accessing the subtree of this point, change the values of top and this point back.


CODE:

 

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 using namespace std;
 5 const int N = 3e5 + 12;
 6 typedef long long LL;
 7 int n,dt,head[N],que[N];
 8 LL f[N],d[N],v[N],w[N];
 9 struct Edge
10 {
11     int to,nex;
12     LL w;
13 } edge[N << 1];
14 void AddEdge(int u,int v,LL w)
15 {
16     edge[++dt] = (Edge)
17     {
18         v,head[u],w
19     };
20     head[u] = dt;
21 }
22 LL x(int i)
23 {
24     return d[i];
25 }
26 LL y(int i)
27 {
28     return f[i];
29 }
30 LL Get(int A,int B)
31 {
32     return f[A] + (d[B] - d[A]) * v[B] + w[B];
33 }
34 double slope(int A,int B)
35 {
36     return ((double)(y(B) - y(A))) / ((double)(x(B) - x(A)));
37 }
38 bool Cross(int A,int B,int C)
39 {
40     return slope(B,C) <= slope(A,B);
41 }
42 int find(int x,int tp)
43 {
44     int l=1,r=tp-1,ret=tp,mid;
45     // Be careful ret Initial value
46     while(l <= r)
47     {
48         mid = l + r >> 1;
49         if(slope(que[mid],que[mid+1]) > (double)v[x]) ret=mid,r=mid-1;
50         else l = mid + 1;
51     }
52     return ret;
53 }
54 
55 int Find(int z,int tp)
56 {
57     int l=0,r=tp-1,ret=tp+1;
58     // Be careful ret Initial value
59     while(l<=r)
60     {
61         int mid =l+r>>1;
62         if(slope(que[mid],z)<=slope(que[mid],que[mid+1]))ret=mid+1,r=mid-1;
63         else l=mid+1;
64     }
65     return ret;
66 }
67 
68 void dfs(int u,int pos,int fa)
69 {
70     int qpos,qtop;
71     f[u] = Get(que[find(u,pos)],u);
72     qpos = Find(u,pos);
73     qtop = que[qpos];
74     que[qpos] = u;
75     for(int i = head[u]; i; i = edge[i].nex)
76     {
77         if(edge[i].to == fa)continue;
78         d[edge[i].to] = d[u] + edge[i].w;
79         dfs(edge[i].to,qpos,u);
80     }
81     que[qpos] = qtop;
82 }
83 int main()
84 {
85     scanf("%d",&n);
86     int x,y,z;
87     for(int i = 1; i < n; i++)
88     {
89         scanf("%d %d %d",&x,&y,&z);
90         AddEdge(x,y,z);
91         AddEdge(y,x,z);
92     }
93     for(int i = 2; i <= n; i++)scanf("%lld %lld",&w[i],&v[i]);
94     dfs(1,0,0);
95     printf("%lld",f[2]);
96     for(int i = 3; i <= n; i++)printf(" %lld",f[i]);
97 }

Tags: PHP shell

Posted on Fri, 01 Nov 2019 19:47:00 -0700 by JDBurnZ