~~不要因为我的马蜂而迷恋我~~
by 范·达克霍姆 @ 2021-10-06 15:07:24
什么玩意 (
by Yikara @ 2021-10-06 15:07:50
这马蜂雀食挺像臭袜子的
by 想吃小熊饼干 @ 2021-10-06 15:08:09
这。。。感觉比P6660第一篇题解还毒瘤。。。
by HYdroKomide @ 2021-10-06 15:09:59
帮lz格式化了一下:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 9;
int a[maxn], head[maxn], num_edge = 0, n, m, root, mods, num_t = 0, siz[maxn], f[maxn], dep[maxn], top[maxn],
tid[maxn], ys[maxn], heavy[maxn], num_T;
struct Edge {
int nxt, to;
} edge[maxn];
void add_edge(int from, int to) {
edge[++num_edge] = (Edge){ head[from], to };
head[from] = num_edge;
}
struct Tree {
int ls, rs;
long long w, tag;
} tree[maxn];
void init(int now, int fa) {
siz[now] = 1;
f[now] = fa;
dep[now] = dep[fa] + 1;
for (int i = head[now]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == fa) {
continue;
}
init(to, now);
siz[now] += siz[to];
if (heavy[now] == 0 || siz[to] > siz[heavy[now]]) {
heavy[now] = to;
}
}
}
void Tdfs(int now, int tp) {
top[now] = tp;
tid[now] = ++num_T;
ys[num_T] = a[now];
if (heavy[now]) {
Tdfs(heavy[now], tp);
}
for (int i = head[now]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (to == f[now]) {
continue;
}
if (to == heavy[now]) {
continue;
}
Tdfs(to, to);
}
};
void wglj(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
x = f[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
} //模板
void push_up(int now) { tree[now].w = tree[tree[now].ls].w + tree[tree[now].rs].w; }
void push_down(int now, int l, int r) {
int mid = (l + r) >> 1;
tree[tree[now].ls].w += ((mid - l + 1) * tree[now].tag) % mods;
tree[tree[now].ls].tag += tree[now].tag;
tree[tree[now].rs].w += ((r - mid) * tree[now].tag) % mods;
tree[tree[now].ls].tag += tree[now].tag;
}
void build(int now, int l, int r) {
if (l == r) {
tree[now].w = ys[l] % mods;
return;
}
int mid = (l + r) >> 1;
tree[now].ls = ++num_t;
tree[now].rs = ++num_t;
build(tree[now].ls, l, mid);
build(tree[now].rs, mid + 1, r);
push_up(now);
}
void update(int now, int l, int r, int lx, int rx, int k) {
if (lx <= l && r <= rx) {
tree[now].w += (r - l + 1) * k % mods;
tree[now].tag += k;
return;
}
int mid = (l + r) >> 1;
push_down(now, l, r);
if (lx <= mid) {
update(now, l, mid, lx, rx, k);
}
if (rx > mid) {
update(now, mid + 1, r, lx, rx, k);
}
push_up(now);
}
long long query(int now, int l, int r, int lx, int rx) {
long long ans = 0;
if (lx <= l && r <= rx) {
ans += tree[now].w;
return ans;
}
int mid = (l + r) >> 1;
push_down(now, l, r);
if (lx <= mid) {
query(now, l, mid, lx, rx) % mods;
}
if (r > mid) {
query(now, mid + 1, r, lx, rx);
}
return ans;
}
void tupdate1(int x, int y, int k) {
k %= mods;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) {
swap(x, y);
}
update(1, 1, n, tid[top[x]], tid[x], k);
x = f[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
update(1, 1, n, tid[x], tid[y], k);
}
void tupdate2(int x, int k) {
k %= mods;
update(1, 1, n, tid[x], tid[x] + siz[x] - 1, k);
}
long long tquery1(int x, int y) {
long long ans = 0;
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[x]]) {
swap(x, y);
}
long long res = query(1, 1, n, tid[top[x]], tid[x]);
ans = (ans + res) % mods;
x = f[top[x]];
}
if (dep[x] > dep[y]) {
swap(x, y);
}
long long res = query(1, 1, n, tid[x], tid[y]);
ans = (ans + res) % mods;
return ans;
}
long long tquery2(int x) {
long long ans = query(1, 1, n, tid[x], tid[x] + siz[x] - 1);
return ans % mods;
}
int main() {
cin >> n >> m >> root >> mods;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
add_edge(u, v);
add_edge(v, u);
}
init(root, 0);
Tdfs(root, root);
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int op, x, y, z;
scanf("%d %d", &op, &x);
if (op == 1) {
scanf("%d %d", &y, &z);
tupdate1(x, y, z);
} else if (op == 2) {
scanf("%d", &y);
printf("%d\n", tquery1(x, y));
} else if (op == 3) {
scanf("%d%d", &x, &z);
cout << "!@#@!#" << i << endl;
tupdate2(x, z);
} else if (op == 4) {
scanf("%d", &x);
printf("%d\n", tquery2(x));
}
return 0;
}
}
```
by Ew_Cors @ 2021-10-06 15:12:01
这马蜂不能说想 `shi` 一样吧……总之比 `shi` 还令人发口区
by 无咕_ @ 2021-10-06 15:12:05
@[Ew_Cors](/user/180103) %%%
by sycqwq @ 2021-10-06 15:12:28
@[Ew_Cors](/user/180103) 没,他马蜂就是那样(真的)
by 无咕_ @ 2021-10-06 15:12:36
只能说大家评价的都很客观
by 鹿目圆 @ 2021-10-06 15:13:37
@[Ew_Cors](/user/180103) T口T
by 范·达克霍姆 @ 2021-10-06 15:14:26