小豪的花园

Posted on In

题目大意:小豪每个花棚里有一定数量的花 ai,即形成树结构，其中根节点是 1 号花棚。现在小豪打算重新分配每个花棚里花的数量。为了能方便快捷地知道花园的情况，小豪现在需要你的帮助。具体地说，小豪共有 m 个操作。操作有三种：

1 u k 表示如果一个花棚在以 u 号花棚为根的子树中，那么小豪会把这个花棚花的数量 模 k；

2 u x 表示小豪将 u 号花棚花的数量变成 x；

3 u v 表示小豪询问从 u 号花棚走到 v 号花棚总共能看到的花的数量。

说白了就是给你一棵树,让你维护三种操作:单点修改,区间修改,区间查询

这种东西就是得多写多做

区间取模的话,就是维护一个最大值,方便处理,如果发现区间最大值小于这个模数,那么就可以跳过了,否则暴力修改

代码如下: 

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
#include <bits/stdc++.h>
#define int long long
#define ll long long
using namespace std;

const int N = 1e5 + 66;

inline ll read()
{
    ll s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(ll x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

int ver[N << 1], nex[N << 1], head[N], cnt;

inline void add_edge(int x, int y)
{
    ver[++ cnt] = y;
    nex[cnt] = head[x];
    return (void)(head[x] = cnt);
}

int n, m;
int fa[N], siz[N], dep[N], son[N];
int dfn[N], top[N], a[N], v[N], tot;

struct SEGMENTTREE
{
    int dat, maxv;
}tree[N << 2];

inline void dfs1(int x, int yhm_fa)
{
    int i, y;
    siz[x] = 1;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == yhm_fa) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs1(y, x);
        siz[x] += siz[y];
        if (siz[y] > siz[son[x]]) son[x] = y;
    }
    return;
}

inline void dfs2(int x, int yhm_top)
{
    dfn[x] = ++ tot, a[tot] = v[x];
    top[x] = yhm_top;
    if (! son[x]) return;
    dfs2(son[x], yhm_top);
    int i, y;
    for (i = head[x]; i; i = nex[i])
    {
        y = ver[i];
        if (y == son[x] || y == fa[x]) continue;
        dfs2(y, y);
    }
    return;
}

inline void up(int p)
{
    int l = p << 1, r = (p << 1) | 1;
    tree[p].dat = tree[l].dat + tree[r].dat;
    return (void)(tree[p].maxv = max(tree[l].maxv, tree[r].maxv));
}

inline void build(int p, int l, int r)
{
    if (l == r) return (void)(tree[p].dat = tree[p].maxv = a[l]);
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build((p << 1) | 1, mid + 1, r);
    return (void)(up(p));
}

inline void updata(int p, int l, int r, int nl, int nr, int c)
{
    if (nl <= l && nr >= r && c > tree[p].maxv) return;
    if (l == r) return (void)(tree[p].dat %= c, tree[p].maxv %= c);
    int mid = (l + r) >> 1;
    if (nl <= mid) updata(p << 1, l, mid, nl, nr, c);
    if (nr > mid) updata((p << 1) | 1, mid + 1, r, nl, nr, c);
    return (void)(up(p));
}

inline void bianch(int p, int l, int r, int k, int c)
{
    if (l == r) return (void)(tree[p].dat = tree[p].maxv = c);
    int mid = (l + r) >> 1;
    if (k <= mid) bianch(p << 1, l, mid, k, c);
    else bianch((p << 1) | 1, mid + 1, r, k, c);
    return (void)(up(p));
}

inline int query(int p, int l, int r, int nl, int nr)
{
    if (nl <= l && nr >= r) return tree[p].dat;
    int mid = (l + r) >> 1, res(0);
    if (nl <= mid) res = query(p << 1, l, mid, nl, nr);
    if (nr > mid) res += query((p << 1) | 1, mid + 1, r, nl, nr);
    return res;
}

inline int query_path(int x, int y)
{
    int res(0);
    while (top[x] != top[y])
    {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        res += query(1, 1, n, dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if (dep[x] < dep[y]) swap(x, y);
    res += query(1, 1, n, dfn[y], dfn[x]);
    return res;
}

signed main()
{
    int i, x, y, opt;
    n = read(), m = read();
    for (i = 1; i < n; ++ i)
    {
        x = read(), y = read();
        add_edge(x, y), add_edge(y, x);
    }
    for (i = 1; i <= n; ++ i) v[i] = read();

    dep[1] = 1;
    dfs1(1, 0), dfs2(1, 1);
    build(1, 1, n);

    for (i = 1; i <= m; ++ i)
    {
        opt = read(), x = read();
        if (opt == 1) y = read(), updata(1, 1, n, dfn[x], dfn[x] + siz[x] - 1, y);
        if (opt == 2) y = read(), bianch(1, 1, n, dfn[x], y);
        if (opt == 3) y = read(), put(query_path(x, y));
    }

    return 0;
}
/*
End...
the first is correct!
*/

后记:

代码巨长,细节巨多

但是我一次写对了,开心

纪念于此,不枉存在