RabbieWjy's blog
0%

NOI2014 购票

发表于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟
这道题似乎有很多做法，这里写的是点分治做法~

题目链接：洛谷；LOJ。

一眼看错题目的式子，$dp_v+q_v$ 其实是 $d\cdot p_v+q_v$
(

每个点要往上跳，考虑 DP，点 $u$ 可以从深度大于等于某个值的祖先 $v$ 转移：$f_u = \min { f_v + dis(u,v) p_u + q_u } = \min { f_v + dep(u) p_u - dep(v)p_u + q_u } = \min { f_v - dep(v)p_u } + dep(u)p_u + q_u$。直接斜率优化，$dep(v)$ 有单调性，维护下凸壳，二分找转移点，可以解决链的情况。

考虑怎么放到树上，这里写点分治的做法。有根树上的点分治和无根树上的很像，只是计算下面的点需要先算好上面的点，有一个先后顺序。于是可以先算上面的一部分，再算上面对下面的贡献，最后再算下面。具体步骤如下：

  1. 找当前求解的块的重心作为分治中心；
  2. 递归求解重心以上的部分（也就是看成重心为根的树后，包括原来的根的那一棵子树）；
  3. 算上面部分对下面所有点的贡献；
  4. 递归求解重心的子树。

第三步与 cdq 分治算贡献的操作类似（是一样的吗？）。分析时间复杂度，每次递归，块的大小都会减半，总共 $O(\log n)$ 层，每一层的总大小都是 $O(n)$。每层中第三步的时间复杂度为 $O(n \log n)$，总时间复杂度为 $O(n \log^2 n)$。

需要注意的细节有：每次用到的连通块是否包含重心；连通块大小为 $2$ 时小心重心不停选同一个点，导致每次递归都是一样的连通块，死循环。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <cstdio>
#include <algorithm>
#define Pair pair <long long, long long>
using namespace std;

typedef long long ll;
const ll inf = 5e17;

int n,t;
int to[400010],nxt[400010],head[200010],cnt;
ll p[200010],q[200010];
ll val[400010];
int st[200010],tp;
ll dis[200010],lim[200010],dep[200010];
int siz[200010],maxsiz[200010],nsiz,root,vis[200010];
int ind[200010],len;
Pair wai[200010],st2[200010];
int lenwai;
ll f[200010];

void add(int x,int y,int z)
{
    to[++ cnt] = y;
    val[cnt] = z;
    nxt[cnt] = head[x];
    head[x] = cnt;
}

void pre(int x,int la)
{
    st[++ tp] = x;
    int l = 1,r = tp,res = 0;
    siz[x] = 1;
    while (l <= r)
    {
        int mid = ((l + r) >> 1);
        if (dis[x] - dis[st[mid]] <= lim[x]) res = mid,r = mid - 1;
        else l = mid + 1;
    }
    lim[x] = dep[st[res]];
    for (int i = head[x];i;i = nxt[i])
    {
        int u = to[i];
        if (u == la) continue;
        dis[u] = dis[x] + val[i];
        dep[u] = dep[x] + 1;
        pre(u,x);
        siz[x] += siz[u];
    }
    tp --;
}

void fndroot(int x)
{
    siz[x] = 1;
    maxsiz[x] = 0;
    if (vis[x]) return ;
    for (int i = head[x];i;i = nxt[i])
    {
        int u = to[i];
        if (dep[u] < dep[x]) continue;
        fndroot(u);
        maxsiz[x] = max(maxsiz[x],siz[u]);
        siz[x] += siz[u];
    }
    maxsiz[x] = max(maxsiz[x],nsiz - siz[x]);
    if (siz[x] > 1 && maxsiz[x] < maxsiz[root]) root = x;
}

bool getchain(int x,int ed)
{
    ind[++ len] = x;
    if (x == ed) return true;
    for (int i = head[x];i;i = nxt[i])
    {
        int u = to[i];
        if (dep[u] < dep[x]) continue;
        if (getchain(u,ed)) return true;
    }
    len --;
    return false;
}

long double calk(Pair x,Pair y)
{
    return (long double)1.0 * (y.second - x.second) / (y.first - x.first);
}

bool pd(Pair x,Pair y,Pair z)
{
    return calk(x,y) >= calk(x,z);
}

void solve(int x,int stdep)
{
    int tmp = max(1ll,lim[x] - stdep + 1);
    wai[++ lenwai] = make_pair(tmp,x);
    for (int i = head[x];i;i = nxt[i])
    {
        int u = to[i];
        if ((x != root && vis[x]) || dep[u] < dep[x]) continue;
        solve(u,stdep);
    }
}

void dfz(int rt)// 点分治
{
    root = 0;
    maxsiz[0] = n + 1;
    nsiz = siz[rt];
    if (nsiz == 1 || vis[rt]) return ;
    fndroot(rt);
    int tmp = root;
    vis[root] = 1;
    dfz(rt);// 算根到重心以上的树的答案
    root = tmp;
    len = 0;
    getchain(rt,root);// 把根到重心的链拉出来
    lenwai = 0;
    solve(root,dep[rt]);
    sort(wai + 1,wai + lenwai + 1,[](Pair x,Pair y){return x.first > y.first;});
    int la = len;
    tp = 0;
    for (int i = 1;i <= lenwai;i ++)
    {
        Pair x = wai[i];
        for (int j = la;j >= x.first;j --)
        {
            ll X = dis[ind[j]],Y = f[ind[j]];
            while (tp > 1 && pd(make_pair(X,Y),st2[tp],st2[tp - 1])) tp --;
            st2[++ tp] = make_pair(X,Y);
        }
        la = min(len,(int)x.first - 1);
        int l = 1,r = tp,res = 0;
        long double K = p[x.second];
        while (l <= r)
        {
            int mid = ((l + r) >> 1);
            if (mid == 1 || calk(st2[mid],st2[mid - 1]) >= K) res = mid,l = mid + 1;
            else r = mid - 1;
        }
        if (res) f[x.second] = min(f[x.second],st2[res].second - p[x.second] * st2[res].first + dis[x.second] * p[x.second] + q[x.second]);
    }
    for (int i = head[root];i;i = nxt[i])
    {
        int u = to[i];
        if (dep[u] > dep[root]) dfz(u);
    }
}

int main()
{
    scanf("%d%d",&n,&t);
    for (int i = 2;i <= n;i ++)
    {
        int x,y;
        scanf("%d%d%lld%lld%lld",&x,&y,p + i,q + i,lim + i);
        add(x,i,y),add(i,x,y);
    }
    for (int i = 2;i <= n;i ++) f[i] = inf;
    pre(1,0);// 预处理每个点最高可以从哪个祖先转移过来
    dfz(1);
    for (int i = 2;i <= n;i ++) printf("%lld\n",f[i]);
}