2019南昌邀请赛网络赛 J题 Distance on the tree 边权树剖 + 树上DFS序建主席树

传送门：https://nanti.jisuanke.com/t/38229

题意

给n个点，n-1条边，每条边都有边权。 m此询问，输出u到v这条简单路径上边权<=k的边数。

思路

首先看到这道题，找到几个关键点。u到v、区间小于k的个数

  • u到v的简单路径，可以树剖将树化为数列进行模拟.
  • 区间<=k的个数，在树的dfs序上建主席树。

这题是边权，我们树剖完成之后，根据每个节点的深度，将边权给儿子作为点权。 根节点1就没有权值，所以我们将根节点的点权设为最大值，使主席树不影响。

然后根据dfs序，建n颗主席树，最后利用前缀和的思想，得出答案。

root[0]这棵初始主席树建不建无所谓，都ok。

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
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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197

##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define lc u << 1
##define rc u << 1  1
##define mid (t[u].l + t[u].r) / 2
##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
// const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

const int maxn = 1e5 + 10;
const int N = 1e5 + 10;

/*-------------------建边-----------------*/

struct Edge {
    int v, next;
}e[maxn << 1];
int head[maxn << 1], t;
int eg[N << 1][3];

inline void add(int u, int v) {
    e[++t].v = v;
    e[t].next = head[u];
    head[u] = t;
}

/*-------------------轻重链剖分-----------------*/

int dep[N], siz[N], fa[N], son[N];

void dfs1(int u, int par) {
    dep[u] = dep[fa[u] = par] + (siz[u] = 1);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == par) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(!son[u]  siz[v] > siz[son[u]])
            son[u] = v;
    }
}

int tim, dfn[N], nodeof[N], top[N];

void dfs2(int u, int topf) {
    nodeof[dfn[u] = ++tim] = u;
    top[u] = topf;
    if(!son[u]) return ;
    dfs2(son[u], topf);
    for(int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if(v == fa[u]  v == son[u]) continue;
        dfs2(v, v);
    }
}

/*-------------------树上主席树-----------------*/

int n, m;
int a[N];
vector<int> v;
int cnt, root[N];

struct Tree {
    int l, r;
    int sum;
}hjt[N * 40];

inline int getid(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; }

void build(int &now, int l , int r) {
    now = ++cnt;
    if(l == r) return ;
    int m = (l + r) >> 1;
    build(hjt[now].l, l, m);
    build(hjt[now].r, m + 1, r);
}

void insert(int pre, int &now, int l, int r, int p) {
    hjt[now = ++cnt] = hjt[pre];
    hjt[now].sum++;
    if(l == r) {
        return ;
    }
    int m = (l + r) >> 1;
    if(p <= m) insert(hjt[pre].l, hjt[now].l, l, m, p);
    else insert(hjt[pre].r, hjt[now].r, m + 1, r, p);
}

int query(int L, int R, int l, int r, int k) {
    if(l == r) return hjt[R].sum - hjt[L].sum;
    int m = (l + r) >> 1;

    int ans = 0;
    if(k <= m) ans += query(hjt[L].l, hjt[R].l, l, m, k);
    else {
        ans += hjt[hjt[R].l].sum - hjt[hjt[L].l].sum;
        ans += query(hjt[L].r, hjt[R].r, m + 1, r, k);
    }
    return ans;
}

int query_chain(int x, int y, int k) {
    int ans = 0;
    while(top[x] != top[y]) {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += query(root[dfn[top[x]] - 1], root[dfn[x]], 1, n, k);
        x = fa[top[x]];
    }
    if(x == y) return ans;
    if(dep[x] > dep[y]) swap(x, y);
    ans += query(root[dfn[x]], root[dfn[y]], 1, n, k);
    return ans;
}

void solve() {
    scanf("%d%d",&n,&m);
    // 剖分
    for(int i = 1;i < n; i++) {
        int u, v, w;
        scanf("%d%d%d",&u,&v,&w);
        add(u, v);
        add(v, u);
        eg[i][0] = u; eg[i][1] = v; eg[i][2] = w;
    }
    dfs1(1, 0);
    dfs2(1, 1);
    // 建树
    for(int i = 1;i < n; i++) {
        if(dep[eg[i][0]] > dep[eg[i][1]]) swap(eg[i][0], eg[i][1]);
        a[eg[i][1]] = eg[i][2];
        v.push_back(eg[i][2]);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    build(root[0], 1, n);
    for(int i = 1;i <= n; i++) {
        int x = getid(a[nodeof[i]]);
        if(i == 1) x = n + 1;
        insert(root[i - 1], root[i], 1, n, x);
    }
    // 查询
    while(m--) {
        int l, r, k;
        scanf("%d%d%d",&l,&r,&k);
        k = upper_bound(v.begin(), v.end(), k) - v.begin() + 1; // 第一个比k大于等于的数的下标
        k--;
        if(k == 0) {
            printf("0\n");
            continue;
        }
        printf("%d\n",query_chain(l, r, k));
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
//    int size=40<<20;
//    __asm__ ("movq %0,%%rsp\n"::"r"((char*)malloc(size)+size));
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    signed test_index_for_debug = 1;
    char acm_local_for_debug = 0;
    do {
        if (acm_local_for_debug == '$') exit(0);
        if (test_index_for_debug > 20)
            throw runtime_error("Check the stdin!!!");
        auto start_clock_for_debug = clock();
        solve();
        auto end_clock_for_debug = clock();
        cout << "Test " << test_index_for_debug << " successful" << endl;
        cerr << "Test " << test_index_for_debug++ << " Run Time: "
             << double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
        cout << "--------------------------------------------------" << endl;
    } while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
    solve();
##endif
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2020/12/23/2019-icpc-nanchang-yaoqing-j/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！