BZOJ3784 树上的路径 <点分治序+ST表+堆>

Posted on Symbols count in article: 1.1k Reading time ≈ 4 mins.

Problem

树上的路径

Time  Limit:  10  Sec\mathrm{Time\;Limit:\;10\;Sec}
Memory  Limit:  256  MB\mathrm{Memory\;Limit:\;256\;MB}

Description

给定一个NN个结点的树，结点用正整数1∼N1\sim N编号，每条边有一个正整数权值。
用d(a,b)d(a,b)表示从结点aa到结点bb路边上经过边的权值，其中要求a<ba<b。
将这n×(n−1)2\frac{n\times(n-1)}{2}个距离从大到小排序，输出前MM个距离值。

Input

第一行两个正整数N,MN,M。
下面N−1N-1行，每行三个正整数a,b,c  (a,b≤N,  c≤10000)a,b,c\;(a,b\le N,\;c\le10000)，表示结点aa到结点bb有一条权值为cc的边。

Output

共MM行，如题所述。

Sample Input

1
2
3
4
5
5 10
1 2 1
1 3 2
2 4 3
2 5 4

Sample Output

1
2
3
4
5
6
7
8
9
10
7
7
6
5
4
4
3
3
2
1

Hint

N≤5×104,  M≤min⁡(3×105,n×(n−1)2)N\le 5\times10^4,\;M\le \min(3\times10^5,\frac{n\times(n-1)}{2})

标签：点分治序 ST表 堆

Solution

BZOJ2006超级钢琴\mathrm{BZOJ2006超级钢琴}的加强版，将问题移到了树上。

对于关系到树上所有路径的问题，一般用点分治解决。此题需要用到点分治序。
点分时，记录下每个分治中心，并在从分治中心向外DFS\mathrm{DFS}的过程中记录下走到结点的顺序，这样的排列叫做点分治序。其实就是点分树上的DFS\mathrm{DFS}序中插入每个点子树的DFS\mathrm{DFS}序。

对于一个分治中心uu，其在点分治序上的第xx个位置出现，并且从uu开始做DFS\mathrm{DFS}，每个子树的DFS\mathrm{DFS}序分别在位置区间x+1∼x+sz1x+1\sim x+sz_1，x+sz1+1∼x+sz1+sz2x+sz_1+1\sim x+sz_1+sz_2，x+sz1+sz2+1∼x+sz1+sz2+sz3x+sz_1+sz_2+1\sim x+sz_1+sz_2+sz_3…对于uu第ii个子树中的一点vv，以vv为起点，其路径另一端点只能落在点分治序位置区间x∼x+sz1+sz2+⋯+szi−1x\sim x+sz_1+sz_2+\cdots+sz_{i-1}内，发现以每个点为一端，形成的路径的另一端在点分治序上一定对应一个区间。

这样问题又转化到了数列上，即已知对于每个数xx，其二元组(x,y)(x,y)中另一个数yy的范围[l,r][l,r]，二元组(x,y)(x,y)的权值为dx+dyd_x+d_y，求前kk大的二元组权值。

这个问题可以用类似BZOJ2006的方法解决，在此不再赘述。

Code

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
#include <bits/stdc++.h>
#define MAX_N 50000
#define MAX_M 800000
#define LOG Log[t-s]
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, k, rt, tot;
int sz[MAX_N+5], w[MAX_N+5], L[MAX_M+5], R[MAX_M+5];
int d[MAX_M+5], st[MAX_M+5][25], Log[MAX_M+5];
struct node {int p, l, r, val; bool operator < (const node &t) const {return t.val > val;}} ;
vector <int> G[MAX_N+5], E[MAX_N+5]; bool mrk[MAX_N+5]; priority_queue <node> que;
void insert(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c);}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, c);}
void getrt(int u, int fa) {
    sz[u] = 1, w[u] = 0;
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (((v = G[u][i]) ^ fa) && !mrk[v])
            getrt(v, u), sz[u] += sz[v], w[u] = max(w[u], sz[v]);
    if ((w[u] = max(w[u], tot-sz[u])) < w[rt]) rt = u;
}
void getdis(int u, int fa, int dis) {
    d[++m] = dis, L[m] = L[m-1]; if (!R[m]) R[m] = R[m-1];
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (((v = G[u][i]) ^ fa) && !mrk[v])
            getdis(v, u, dis+E[u][i]);
}
void DFS(int u) {
    d[++m] = 0, L[m] = m, R[m] = m-1, mrk[u] = true;
    for (int i = 0, v; i < (int)G[u].size(); i++)
        if (!mrk[v = G[u][i]]) R[m+1] = m, getdis(v, u, E[u][i]);
    for (int i = 0, v; i < (int)G[u].size(); i++) if (!mrk[v = G[u][i]])
        w[rt = 0] = tot = sz[v], getrt(v, u), DFS(rt);
}
int Max(int a, int b) {return d[a] > d[b] ? a : b;}
void init_ST() {
    for (int i = 2; i <= m; i++) Log[i] = Log[i>>1]+1;
    for (int i = 1; i <= m; i++) st[i][0] = i;
    for (int j = 1; (1<<j) <= m; j++)
        for (int i = 1; i <= m-(1<<j)+1; i++)
            st[i][j] = Max(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int query(int s, int t) {return s > t ? -1 : Max(st[s][LOG], st[t-(1<<LOG)+1][LOG]);}
int main() {
    read(n), read(k);
    for (int i = 1, u, v, c; i < n; i++)
        read(u), read(v), read(c), addedge(u, v, c);
    w[rt = 0] = tot = n, getrt(1, 0), DFS(rt), init_ST();
    for (int i = 1; i <= m; i++) if (L[i] <= R[i])
        que.push((node){i, L[i], R[i], d[i]+d[query(L[i], R[i])]});
    for (int i = 1, t, p; i <= k; i++) {
        node tp = que.top(); que.pop(), p = tp.p, printf("%d\n", tp.val);
        int ll = tp.l, rr = tp.r, lr = query(ll, rr)-1, rl = query(ll, rr)+1;
        if (~(t = query(ll, lr))) que.push((node){p, ll, lr, d[p]+d[t]});
        if (~(t = query(rl, rr))) que.push((node){p, rl, rr, d[p]+d[t]});
    }
    return 0;
}