HDU6162

发表于

Description

给出一棵带点权的树，每次询问两点之间路径上权值在$[a_i,b_i]$之间的点权和。

Solution

不知道有没有什么巧妙的做法，反正我是工业了一波。

转有根树，记录每个点到根节点上所有点权的权值线段树，离散化之后可持久化。
在LCA处作差即可。

不知道为什么放到树链剖分里，然后就强行树剖写了一发LCA。
肯定是我太垃圾了。

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
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
bool Read ( int &x, char c = getchar() ) {
    for ( x = 0 ; !isdigit(c) ; c = getchar() ) if (c == EOF) return 0 ;
    for ( ; isdigit(c) ; c = getchar() ) x = 10*x + c - '0' ;
    return 1 ;
}
const int maxn = 1e5+5 ;
int c[maxn], n, m, k, e, Begin[maxn], Next[maxn*2], To[maxn*2] ;
void add ( int x, int y ) {
    To[++e] = y ;
    Next[e] = Begin[x] ;
    Begin[x] = e ;
}
int son[maxn], fa[maxn], dep[maxn], top[maxn], size[maxn] ;
int tot, rt[maxn], b[maxn*4], ch[maxn*30][2] ;
LL tree[maxn*30] ;
#define me(a) memset(a,0,sizeof a)
void init() {
    tot = e = 0 ;
    me(Begin) ;
    me(Next) ;
    me(son) ;
    me(dep) ;
    me(top) ;
    me(size) ;
    me(rt) ;
    me(tree) ;
    me(ch) ;
}
void dfs1 ( int x ) {
    int i, u ;
    size[x] = 1 ;
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        if (size[u]) continue ;
        dep[u] = dep[x]+1 ;
        fa[u] = x ;
        dfs1(u) ;
        size[x] += size[u] ;
        if (son[x] == 0 || size[u] > size[son[x]])
            son[x] = u ;
    }
}
void dfs2 ( int x ) {
    int i, u ;
    if (son[x]) {
        top[son[x]] = top[x] ;
        dfs2(son[x]) ;
    } else return ;
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        if (u == fa[x] || u == son[x]) continue ;
        top[u] = u ;
        dfs2(u) ;
    }
}
int LCA ( int u, int v ) {
    while (top[u] != top[v]) {
        if (dep[top[u]] > dep[top[v]]) swap(u, v) ;
        v = fa[top[v]] ;
    }
    if (dep[u] > dep[v]) swap(u, v) ;
    return u ;
}
struct Qry {
    int u, v, a, b ;
} q[maxn] ;
void push_up ( int x ) {
    tree[x] = 0 ;
    if (ch[x][0]) tree[x] += tree[ch[x][0]] ;
    if (ch[x][1]) tree[x] += tree[ch[x][1]] ;
}
int create ( int l, int r, int v, int value ) {
    int x = ++tot, mid = (l+r)>>1 ;
    if (l == r) {
        tree[x] += value ;
        return x ;
    }
    if (v <= mid) ch[x][0] = create(l, mid, v, value) ;
    else ch[x][1] = create(mid+1, r, v, value) ;
    push_up(x) ;
    return x ;
}
int insert ( int h, int l, int r, int v, int value ) {
    int x = ++tot, mid = (l+r)>>1 ;
    if (l == r) {
        tree[x] += tree[h] ;
        tree[x] += value ;
        return x ; 
    }
    if (v <= mid) {
        ch[x][0] = insert(ch[h][0], l, mid, v, value) ;
        ch[x][1] = ch[h][1] ;
    } else {
        ch[x][0] = ch[h][0] ;
        ch[x][1] = insert(ch[h][1], mid+1, r, v, value) ;
    }
    push_up(x) ;
    return x ;
}
void dfs ( int x ) {
    int i, u ;
    if (fa[x]) rt[x] = insert(rt[fa[x]], 1, k, lower_bound(b+1, b+k+1, c[x])-b, c[x]) ;
    else rt[x] = create(1, k, lower_bound(b+1, b+k+1, c[x])-b, c[x] ) ;
    for ( i = Begin[x] ; i ; i = Next[i] ) {
        u = To[i] ;
        if (u == fa[x]) continue ;
        dfs(u) ;
    }
}
LL query ( int h, int l, int r, int x, int y ) {
    if (h == 0) return 0 ;
    if (x <= l && r <= y) return tree[h] ;
    int mid = (l+r)>>1 ;
    if (y <= mid) return query(ch[h][0], l, mid, x, y) ;
    else if (x > mid) return query(ch[h][1], mid+1, r, x, y) ;
    return query(ch[h][0], l, mid, x, mid)+query(ch[h][1], mid+1, r, mid+1, y) ;
}
LL Query ( int x, int l, int r ) {
    return query(rt[x], 1, k, l, r) ;
}
int main() {
    int i, u, x ;
    LL rec ;
    while (Read(n) && Read(m)) {
        init() ;
        k = 0 ;
        for ( i = 1 ; i <= n ; i ++ ) {
            Read(c[i]) ;
            b[++k] = c[i] ;
        }
        for ( i = 1 ; i < n ; i ++ ) {
            Read(x) ; Read(u) ;
            add(x, u) ;
            add(u, x) ;
        }
        dfs1(1) ;
        top[1] = 1 ;
        dfs2(1) ;
        for ( i = 1 ; i <= m ; i ++ ) {
            Read(q[i].u) ;
            Read(q[i].v) ;
            Read(q[i].a) ;
            Read(q[i].b) ;
            b[++k] = q[i].a ;
            b[++k] = q[i].b ;
        }
        sort(b+1, b+k+1) ;
        k = unique(b+1, b+k+1)-b-1 ;
        dfs(1) ;
        for ( i = 1 ; i <= m ; i ++ ) {
            x = LCA(q[i].u, q[i].v) ;
            rec = 0 ;
            q[i].a = lower_bound(b+1, b+k+1, q[i].a)-b ;
            q[i].b = lower_bound(b+1, b+k+1, q[i].b)-b ;
            rec += Query(q[i].u, q[i].a, q[i].b) ;
            rec += Query(q[i].v, q[i].a, q[i].b) ;
            rec -= Query(x, q[i].a, q[i].b) ;
            if (fa[x]) rec -= Query(fa[x], q[i].a, q[i].b) ;
            printf ( "%lld", rec ) ;
            if (i == m) putchar('\n') ;
            else putchar(' ') ;
        }
    }
    return 0 ;
}