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

Problem

树上的路径

Description

给定一个个结点的树，结点用正整数编号，每条边有一个正整数权值。
用表示从结点到结点路边上经过边的权值，其中要求。
将这个距离从大到小排序，输出前个距离值。

Input

第一行两个正整数。
下面行，每行三个正整数，表示结点到结点有一条权值为的边。

Output

共行，如题所述。

Sample Input

Sample Output

Hint

标签：点分治序 ST表 堆

Solution

的加强版，将问题移到了树上。

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

对于一个分治中心，其在点分治序上的第个位置出现，并且从开始做，每个子树的序分别在位置区间，，……对于第个子树中的一点，以为起点，其路径另一端点只能落在点分治序位置区间内，发现以每个点为一端，形成的路径的另一端在点分治序上一定对应一个区间。

这样问题又转化到了数列上，即已知对于每个数，其二元组中另一个数的范围，二元组的权值为，求前大的二元组权值。

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

Code

#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;
}