跳转至

BZOJ3307

Bzoj3307 雨天的尾巴ψ(｀∇´)ψ

\(\text{Question}\)ψ(｀∇´)ψ

给定一棵树，每次给 \((x,y)\) 的简单路径上的节点发放一个第 \(z\) 种物品。

\(M\) 次操作，最后询问每个点最多的是哪一种物品。

\(1\le N,M \le 10^5,1\le z\le 10^9\)

\(\text{Brute force}\)ψ(｀∇´)ψ

先离散化 \(z\)。

考虑设一个计数数组 \(d\)，对于每个节点 \(x\)，分别维护第 \(z\) 种物品在 \(x\) 上有多少个。

先求出 \(\text{LCA}\) ，每次操作从 \(x \to \text{LCA} \to y\) ，然后把路径上相应的节点的 \(d[x][z]\) 加一。

复杂度 \(\text{O}(NM)\)。

或者可以利用树上差分对每种物品的情况分别进行修改。

具体来说，设 \(c\) 为 \(d\) 的差分数组，每次操作 \((x,y,z)\) ，使 ：

\[c[x][z]+1,c[y][z]+1,c[\text{LCA(x,y)}][z]-1,c[\text{Father}(\text{LCA(x,y)})][z]-1\]

最后进行 \(cnt_z\) 次 dfs，对于每个节点 \(u\)，\(d\) 就等于 \(c\) 的子树和

对于每个节点求物品出现次数的最值即可。

复杂度 \(\text{O}(N\times cnt_z)\)，\(cnt_z\) 是不同的物品的数量。

这个做法是对每种物品都维护了一个差分序列，不过这个差分序列是在树上的。

\(\text{Solution}\)ψ(｀∇´)ψ

实际上 \(\text{O}(N\times cnt_z)\) 做法是对每个节点 \(u\) 维护了一个序列 \(c[u]\)，\(c[u][z]\) 就表示 \(z\) 这种物品的差分序列在 \(u\) 这里的这一项。

那么一个节点 \(u\) 的答案就是它子树当中所有节点的 \(c[v]\) 的合并起来之后得到的新序列的 \(\text{max\_element}\)。

所以对于每一个节点 \(u\) 开一颗动态开点线段树代替 \(c[u]\)，同时支持维护 \(c[u]\) 当中的最大值和最大值的位置。

可以发现每个节点的动态开点线段树维护的值域是一样的，都是 \([1,cnt_z]\)。

进行一次 dfs，那么计算 \(u\) 的答案的时候，就只需要把 \(u\) 的所有儿子节点的线段树和 \(u\) 的线段树进行线段树合并即可快速得到 \(u\) 的答案。

复杂度 \(\text{O}((N+M)\log(N+M))\)

\(\text{Trick:}\) 对于树上每个节点维护一个信息序列，并且每个节点的答案可以通过类似子树和的方式得到，可以考虑使用一颗动态开点线段树代替每个节点的信息序列，然后使用线段树合并计算答案。

\(\text{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
 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
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int si = 1e5 + 10;

int n, m;

int tot = 0, head[si];
struct Edge {
    int ver,Next;
}e[si << 1];
inline void add(int u, int v) {
    e[tot] = (Edge){v, head[u]}, head[u] = tot++;
}

int dep[si], f[si][20];
int lg;
inline void dfs1(int u,int fa) {
    dep[u] = dep[fa] + 1, f[u][0] = fa;
    for(int i = 1; i <= lg; ++i) f[u][i] = f[ f[u][i-1] ][i-1];

    for(int i = head[u]; ~i; i = e[i].Next){
        int v = e[i].ver;
        if(v == fa) continue;
        dfs1(v, u);
    }
}
inline int Lca(int u, int v) {
    if(dep[u] < dep[v]) swap(u, v);
    for(int i = lg; i >= 0; --i) if(dep[f[u][i]] >= dep[v]) u = f[u][i];
    if(u == v) return u;

    for(int i = lg; i >= 0; --i) if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
    return f[u][0];
}

int root[si], cnt = 0;
struct segment_tree {
    int ls, rs;
    int mx, id;
}t[si * 80];
inline void pushup(int p) {
    int lc = t[p].ls, rc = t[p].rs;

    if(t[lc].mx >= t[rc].mx) t[p].mx = t[lc].mx, t[p].id = t[lc].id;
    else t[p].mx = t[rc].mx, t[p].id = t[rc].id;
}
inline void change(int &p, int l, int r, int pos, int val) {
    if(!p) p = ++cnt;

    if(l == r){
        t[p].mx += val;
        t[p].id = l;
        return ;
    }

    int mid = l + r >> 1;
    if(pos <= mid) change(t[p].ls, l, mid, pos, val);
    else change(t[p].rs, mid+1, r, pos, val);
    pushup(p);
}
int merge(int p, int q, int l, int r) {
    if(!p) return q; if(!q) return p;

    if(l == r){
        t[p].mx += t[q].mx;
        return p;
    }

    int mid = l + r >> 1;
    t[p].ls = merge(t[p].ls, t[q].ls, l, mid);
    t[p].rs = merge(t[p].rs, t[q].rs, mid+1, r);
    pushup(p); return p;
}

int cntz = 0;
int ans[si];
int u[si], v[si], z[si], idz[si];
void dfs2(int u,int fa) {
    for(int i = head[u]; ~i; i = e[i].Next) {
        int v = e[i].ver;
        if(v == fa) continue;
        dfs2(v, u);
        root[u] = merge(root[u], root[v], 1, cntz);
    }
    ans[u] = t[root[u]].mx == 0 ? 0 : t[root[u]].id; 
    return ;
}

int main() {
    cin >> n >> m, lg = (int)(log(n) / log(2)) + 1;
    memset(head, -1, sizeof head);
    for(int i = 1; i < n; ++i) {
        int u, v; cin >> u >> v;
        add(u, v), add(v, u);
    } 
    dfs1(1, 0);

    for(int i = 1; i <= m; ++i) {
        cin >> u[i] >> v[i] >> z[i];
        idz[i] = z[i];
    }
    sort(idz + 1, idz + 1 + m);
    cntz = unique(idz + 1, idz + 1 + m) - idz - 1;

    for(int i = 1; i <= m ; ++i) {
        int nz = lower_bound(idz + 1, idz + 1 + cntz, z[i]) - idz;
        int lca = Lca(u[i], v[i]);
        int fat = f[lca][0];
        change(root[u[i]], 1, cntz, nz, 1);
        change(root[v[i]], 1, cntz, nz, 1);
        change(root[lca], 1, cntz, nz, -1);
        change(root[fat], 1, cntz, nz, -1);
    } 

    dfs2(1, 0);
    for(int i = 1; i <= n; ++i) cout << idz[ans[i]] << endl;
    return 0;
}

1
Tag : 线段树合并/LCA/树上差分
最后更新: May 9, 2023