@[georgeyu123](/user/731709) 是+= 你好好看看
by peaneevall_kalaa @ 2022-08-09 11:14:10
你的 RangeCount 还是=号
by peaneevall_kalaa @ 2022-08-09 11:14:26
@[zhouershan](/user/615348)
改了还是不行
```cpp
// template
#include <bits/stdc++.h>
using namespace std;
#define debug puts("WLX was killed by gaming design.")
typedef long long ll;
namespace IO {
template <typename _Tp>
inline void read(_Tp& x) {
register char ch = getchar();
register int f = 1;
x = 0;
for (; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 3) + (x << 1) + (ch ^ 48);
x *= f;
}
template <typename _Tp>
inline void write(_Tp x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 ^ 48);
}
template <typename _Tp>
inline void writec(_Tp x, char c) {
write(x), putchar(c);
}
} // namespace IO
using namespace IO;
#define N 4000005
int n, m, rt, mod;
int cnt = 0;
int a[N];
class edge {
public:
int v, nxt;
} E[N];
int head[N];
inline void add_edge(int u, int v) {
E[++cnt] = (edge){v, head[u]}, head[u] = cnt;
}
int dep[N], fa[N], sz[N], ch[N];
// dep : 深度
// fa : 父亲
// sz : 子树大小
// ch: 重儿子
inline void dfs1(int index, int __dep) {
dep[index] = __dep;
sz[index] = 1;
for (int i = head[index]; i; i = E[i].nxt) {
int y = E[i].v;
if (fa[index] == y) continue;
fa[y] = index;
dfs1(y, __dep + 1);
sz[index] += sz[y];
if (sz[y] > sz[ch[index]]) ch[index] = y;
}
}
int top[N], dfn[N], lst[N], tot = 0;
// top : 记录x所在的链的顶端节点
// dfn : 节点的新标号
// lst[x] : 记录修改时候tot为x的最后一次修改所在的节点
inline void dfs2(int index, int __top) {
top[index] = __top;
dfn[index] = ++tot;
lst[tot] = a[index];
if (ch[index] == 0) return;
dfs2(ch[index], __top);
for (int i = head[index]; i; i = E[i].nxt) {
int y = E[i].v;
if (y != ch[index] && y != fa[index]) dfs2(y, y);
}
}
class Seginfo {
public:
int l, r;
ll lt, data;
} seg[N << 2];
#define lson index << 1
#define rson index << 1 | 1
inline void pushup(int index) {
seg[index].data = seg[lson].data + seg[rson].data, seg[index].data %= mod;
}
/*
inline void mark(int index, int l, int r, int k) {
seg[index].data += k * (r - l + 1);
seg[index].lt += k;
return;
}
*/
inline void pushdown(int index) {
if (seg[index].lt != 0) {
// int mid = seg[index].l + seg[index].r >> 1;
// mark(lson, seg[index].l, mid, seg[index].lt);
// mark(rson, mid + 1, seg[index].r, seg[index].lt);
seg[lson].lt = (seg[lson].lt + seg[index].lt) % mod;
seg[rson].lt = (seg[rson].lt + seg[index].lt) % mod;
seg[lson].data = (seg[index].lt * (seg[lson].r - seg[lson].l + 1)) % mod;
seg[rson].data = (seg[index].lt * (seg[rson].r - seg[lson].l + 1)) % mod;
seg[index].lt = 0;
}
}
inline void build(int index, int l, int r) {
seg[index].l = l, seg[index].r = r, seg[index].lt = 0;
if (l == r) {
seg[index].data = lst[l];
return;
}
int mid = l + r >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
pushup(index);
}
inline void change(int index, int l, int r, int k) {
if (l <= seg[index].l && r >= seg[index].r) {
seg[index].data = (k * (seg[index].r - seg[index].l + 1)) % mod;
return;
}
pushdown(index);
int mid = seg[index].l + seg[index].r >> 1;
if (l <= mid) change(lson, l, mid, k);
if (r > mid) change(rson, mid + 1, r, k);
pushup(index);
}
inline int query(int index, int l, int r) {
int ret = 0;
if (l <= seg[index].l && seg[index].r <= r) {
seg[index].data %= mod;
return seg[index].data;
}
int mid = l + r >> 1;
if (l <= mid) ret = (query(lson, l, r) + ret) % mod;
if (r > mid) ret = (query(rson, l, r) + ret) % mod;
return ret % mod;
}
inline void RangeAdd(int u, int v, int k) {
debug;
while (top[u] != top[v]) {
debug;
if (dep[top[u]] < dep[top[v]]) swap(u, v);
debug;
change(1, dfn[top[u]], dfn[u], k);
debug;
u = fa[top[u]];
}
debug;
if (dep[u] > dep[v]) swap(u, v);
change(1, dfn[u], dfn[v], k);
}
inline int RangeCount(int u, int v) {
int ret = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = (ret + query(1, dfn[top[u]], dfn[u])) % mod;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ret = (query(1, dfn[u], dfn[v])) % mod;
return ret;
}
inline void TreeAdd(int index, int k) {
change(1, dfn[index], dfn[index] + sz[index] - 1, k);
}
inline int TreeCount(int index) {
int ret = 0;
ret = query(1, dfn[index], dfn[index] + sz[index] - 1) % mod;
return ret;
}
signed main() {
freopen("sp.in", "r", stdin); // freopen("sp.out", "w", stdout);
debug;
read(n), read(m), read(rt), read(mod);
for (int i = 1; i <= n; ++i) read(a[i]);
debug;
for (int i = 1, x, y; i < n; ++i)
read(x), read(y), add_edge(x, y), add_edge(y, x);
debug;
dfs1(rt, 1), dfs2(rt, rt);
build(1, 1, n);
for (int i = 1; i <= n; ++i) {
printf(
"i = %d, dep = %d, fa = %d, ch = %d, sz = %d, top = %d, dfn = %d, lst "
"= %d\n",
i, dep[i], fa[i], ch[i], sz[i], top[i], dfn[i], lst[i]);
}
debug;
for (int i = 1; i <= m; ++i) {
int opt, x, y, z;
read(opt);
if (opt == 1)
read(x), read(y), read(z), RangeAdd(x, y, z % mod);
else if (opt == 2)
read(x), read(y), writec(RangeCount(x, y), '\n');
else if (opt == 3)
read(x), read(z), TreeAdd(x, z);
else if (opt == 4)
read(x), writec(TreeCount(x), '\n');
debug;
}
return 0;
}
/*
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
*/
```
by georgeyu123 @ 2022-08-09 11:21:56
@[georgeyu123](/user/731709) pushdown 中 data 更新错了吧
by thomaswmy @ 2022-08-09 17:34:42
@[georgeyu123](/user/731709) change 也是
by thomaswmy @ 2022-08-09 17:37:30
@[georgeyu123](/user/731709) query 忘 pushdown 了
by thomaswmy @ 2022-08-09 17:38:10
@[georgeyu123](/user/731709) Rangecount 也是
by thomaswmy @ 2022-08-09 17:41:08
```cpp
// template
#include <bits/stdc++.h>
using namespace std;
#define debug puts(" <-- TO BECONTINUE --> ")
typedef long long ll;
namespace IO {
template <typename _Tp>
inline void read(_Tp& x) {
register char ch = getchar();
register int f = 1;
x = 0;
for (; ch < '0' || ch > '9'; ch = getchar()) f = ch == '-' ? -1 : 1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
x = (x << 3) + (x << 1) + (ch ^ 48);
x *= f;
}
template <typename _Tp>
inline void write(_Tp x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 ^ 48);
}
template <typename _Tp>
inline void writec(_Tp x, char c) {
write(x), putchar(c);
}
} // namespace IO
using namespace IO;
#define N 4000005
int n, m, rt, mod;
int cnt = 0;
int a[N];
class edge {
public:
int v, nxt;
} E[N];
int head[N];
inline void add_edge(int u, int v) {
E[++cnt] = (edge){v, head[u]}, head[u] = cnt;
}
int dep[N], fa[N], sz[N], ch[N];
// dep : 娣卞害
// fa : 鐖朵翰
// sz : 瀛愭爲澶у皬
// ch: 閲嶅効瀛?
inline void dfs1(int index, int __dep) {
dep[index] = __dep;
sz[index] = 1;
for (int i = head[index]; i; i = E[i].nxt) {
int y = E[i].v;
if (fa[index] == y) continue;
fa[y] = index;
dfs1(y, __dep + 1);
sz[index] += sz[y];
if (sz[y] > sz[ch[index]]) ch[index] = y;
}
}
int top[N], dfn[N], lst[N], tot = 0;
// top : 璁板綍x鎵€鍦ㄧ殑閾剧殑椤剁鑺傜偣
// dfn : 鑺傜偣鐨勬柊鏍囧彿
// lst[x] : 璁板綍淇敼鏃跺€檛ot涓簒鐨勬渶鍚庝竴娆′慨鏀规墍鍦ㄧ殑鑺傜偣
inline void dfs2(int index, int __top) {
top[index] = __top;
dfn[index] = ++tot;
lst[tot] = a[index];
if (ch[index] == 0) return;
dfs2(ch[index], __top);
for (int i = head[index]; i; i = E[i].nxt) {
int y = E[i].v;
if (y == ch[index] || y == fa[index]) continue;
else dfs2(y, y);
}
}
class Seginfo {
public:
int l, r;
int lt, data;
} seg[N << 2];
#define lson index << 1
#define rson index << 1 | 1
inline void pushup(int index) {
seg[index].data = (seg[lson].data + seg[rson].data) % mod;
}
/*
inline void mark(int index, int l, int r, int k) {
seg[index].data += k * (r - l + 1);
seg[index].lt += k;
return;
}
*/
inline void pushdown(int index) {
if (seg[index].lt != 0) {
// int mid = seg[index].l + seg[index].r >> 1;
// mark(lson, seg[index].l, mid, seg[index].lt);
// mark(rson, mid + 1, seg[index].r, seg[index].lt);
seg[lson].lt = (seg[lson].lt + seg[index].lt) % mod;
seg[rson].lt = (seg[rson].lt + seg[index].lt) % mod;
(seg[lson].data += seg[index].lt * (seg[lson].r - seg[lson].l + 1)) %= mod;
(seg[rson].data += seg[index].lt * (seg[rson].r - seg[rson].l + 1)) %= mod;
seg[index].lt = 0;
}
}
inline void build(int index, int l, int r) {
seg[index].l = l, seg[index].r = r, seg[index].lt = 0;
if (l == r) {
seg[index].data = lst[l] % mod;
return;
}
int mid = l + r >> 1;
build(lson, l, mid), build(rson, mid + 1, r);
pushup(index);
}
inline void change(int index, int l, int r, int k) {
if (l <= seg[index].l && r >= seg[index].r) {
seg[index].data = (seg[index].data + k * (seg[index].r - seg[index].l + 1)) % mod;
seg[index].lt = (seg[index].lt + k) % mod;
return;
}
pushdown(index);
int mid = seg[index].l + seg[index].r >> 1;
if (l <= mid) change(lson, l, mid, k);
if (r > mid) change(rson, mid + 1, r, k);
pushup(index);
}
inline int query(int index, int l, int r) {
int ret = 0;
if (l <= seg[index].l && seg[index].r <= r) {
seg[index].data %= mod;
return seg[index].data;
}
pushdown(index);
int mid = l + r >> 1;
if (l <= mid) ret = (query(lson, l, r) + ret) % mod;
if (r > mid) ret = (query(rson, l, r) + ret) % mod;
return ret % mod;
}
inline void RangeAdd(int u, int v, int k) {
// debug;
while (top[u] != top[v]) {
// debug;
if (dep[top[u]] < dep[top[v]]) swap(u, v);
// debug;
change(1, dfn[top[u]], dfn[u], k);
// debug;
u = fa[top[u]];
}
// debug;
if (dep[u] > dep[v]) swap(u, v);
change(1, dfn[u], dfn[v], k);
}
inline int RangeCount(int u, int v) {
int ret = 0;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ret = (ret + query(1, dfn[top[u]], dfn[u])) % mod;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ret = (ret + query(1, dfn[u], dfn[v])) % mod;
return ret;
}
inline void TreeAdd(int index, int k) {
change(1, dfn[index], dfn[index] + sz[index] - 1, k);
}
inline int TreeCount(int index) {
int ret = 0;
ret = query(1, dfn[index], dfn[index] + sz[index] - 1) % mod;
return ret;
}
signed main() {
// freopen("sp.in", "r", stdin);
// freopen("sp.out", "w", stdout);
// debug;
read(n), read(m), read(rt), read(mod);
for (int i = 1; i <= n; ++i) read(a[i]), a[i] %= mod;
// debug;
for (int i = 1, x, y; i < n; ++i)
read(x), read(y), add_edge(x, y), add_edge(y, x);
// debug;
dfs1(rt, 1), dfs2(rt, rt);
build(1, 1, n);
/*
for (int i = 1; i <= n; ++i) {
printf(
"i = %d, dep = %d, fa = %d, ch = %d, sz = %d, top = %d, dfn = %d, lst "
"= %d\n",
i, dep[i], fa[i], ch[i], sz[i], top[i], dfn[i], lst[i]);
}
*/
for (int i = 1; i <= m; ++i) {
int opt, x, y, z;
read(opt);
if (opt == 1)
debug, read(x), read(y), read(z), debug, RangeAdd(x, y, z % mod);
else if (opt == 2)
read(x), read(y), writec(RangeCount(x, y), '\n');
else if (opt == 3)
read(x), read(z), TreeAdd(x, z);
else if (opt == 4)
read(x), writec(TreeCount(x), '\n');
// cout << "CASE #" << i << ": " << debug;
}
return 0;
}
/*
5 5 2 24
7 3 7 8 0
1 2
1 5
3 1
4 1
3 4 2
3 2 2
4 5
1 5 1 3
2 1 3
*/
```
@[thomaswmy](/user/531319) 还是有问题
by georgeyu123 @ 2022-08-09 18:59:11
[更新地址](https://www.luogu.com.cn/paste/vtoq6vha)
by georgeyucjr @ 2022-08-09 19:02:01
@[georgeyu123](/user/731709) query 的第一个if 写错了
by thomaswmy @ 2022-08-09 19:59:40