蒟蒻看了好久没看出来哪里错了 ……但是和同学的进行中间数据输出的对比时发现建树貌似错了……但是看不出来哪里错了……
dfs和build函数可能错了……但是看不出来 求大佬解答
#include<bits/stdc++.h>
using namespace std;
struct cccp
{
int tg, s;
}t[500010];
int a[100010];
int n, m, s, mo, querys;
int nxt[200010], h[200010], ver[200010], tot;
int dep[100010], fa[100010], son[100010], siz[100010], newid[100010], cnt, nws[100010], top[100010];
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < '0' || c>'9')
{
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ '0');
c = getchar();
}
return x * f;
}
inline void add(int x, int y)
{
tot++;
nxt[tot] = h[x];
h[x] = tot;
ver[tot] = y;
}
inline void build(int x, int l, int r)
{
if (l == r)
{
t[x].s = nws[l];
t[x].s %= mo;
return;
}
int mid = (l + r) >> 1;
build(x * 2, l, mid);
build(x * 2 + 1, mid + 1, r);
t[x].s = t[x * 2].s + t[x * 2 + 1].s;
t[x].s %= mo;
return;
}
inline void pushdown(int x, int l, int r)
{
if (t[x].tg == 0) return;
int mid = (l + r) >> 1;
t[x * 2].tg += t[x].tg;
t[x * 2 + 1].tg += t[x].tg;
t[x * 2].s += t[x].tg * (mid - l + 1);
t[x * 2 + 1].s += t[x].tg * (r - mid);
t[x * 2].s %= mo;
t[x * 2 + 1].s %= mo;
t[x].tg = 0;
return;
}
inline void modify(int x, int el, int er, int l, int r, int k)
{
if (l >= el && r <= er)
{
t[x].s += (r - l + 1) * k;
t[x].s %= mo;
t[x].tg += k;
return;
}
pushdown(x, l, r);
int mid = (l + r) >> 1;
if (el <= mid)
{
modify(x * 2, el, er, l, mid, k);
}
if (er > mid)
{
modify(x * 2 + 1, el, er, mid + 1, r, k);
}
t[x].s = t[x * 2].s + t[x * 2 + 1].s;
t[x].s %= mo;
return;
}
inline int query(int x, int el, int er, int l, int r)
{
if (l >= el && r <= er)
{
return t[x].s;
}
pushdown(x, l, r);
int mid = (l + r) >> 1;
if (el <= mid)
{
querys += query(x * 2, el, er, l, mid);
querys %= mo;
}
if (er > mid)
{
querys += query(x * 2 + 1, el, er, mid + 1, r);
querys %= mo;
}
querys %= mo;
return querys;
}
inline int search(int x, int y)//查询链
{
int ans = 0;
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]]) swap(x, y);
querys = 0;
query(1, newid[top[x]], newid[x], 1, n);
ans += querys;
ans = ans % mo;
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
querys = 0;
query(1, newid[x], newid[y], 1, n);
ans += querys;
ans = ans % mo;
return ans % mo;
}
inline void modify2(int x, int y, int k)//修改链
{
while (top[x] != top[y])
{
if (dep[top[x]] < dep[top[y]])
{
swap(x, y);
}
modify(1, newid[top[x]], newid[x], 1, n, k);
x = fa[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
modify(1, newid[x], newid[y], 1, n, k);
}
inline void modifyson(int x, int k)//改儿子
{
modify(1, newid[x], newid[x] + siz[x] - 1, 1, n, k);
}
inline int searchson(int x)//查儿子
{
querys = 0;
query(1, newid[x], newid[x] + siz[x] - 1, 1, n);
return querys;
}
inline void dfs1(int x, int f)
{
int maxs = -1;
dep[x] = dep[f] + 1;
fa[x] = f;
siz[x] = 1;
for (int i = h[x];i != 0;i = nxt[i])
{
int y = ver[i];
if (y == f) continue;
dfs1(y, x);
siz[x] += siz[y];
if (siz[y] > maxs)
{
maxs = siz[y];
son[x] = y;
}
}
}
inline void dfs2(int x, int tf)
{
newid[x] = ++cnt;
nws[cnt] = a[x];
top[x] = tf;
if (son[x] == 0) return;
dfs2(son[x], tf);
for (int i = h[x];i != 0;i = nxt[i])
{
int y = ver[i];
if (y == fa[x] || y == son[x]) continue;
dfs2(y, y);
}
}
int main()
{
n = read();
m = read();
s = read();
mo = read();
for (int i = 1;i <= n;++i)
{
a[i] = read();
}
for (int i = 1;i < n;++i)
{
int x = read(), y = read();
add(x, y);
add(y, x);
}
dfs1(s, 0);
dfs2(s, s);
build(1, 1, n);
for (int i = 1;i <= m;++i)
{
int qwq = read();
if (qwq == 1)
{
int x = read(), y = read(), z = read();
modify2(x, y, z);
}
if (qwq == 2)
{
int x = read(), y = read();
printf("%d\n", search(x, y));
}
if (qwq == 3)
{
int x = read(), y = read();
modifyson(x, y);
}
if (qwq == 4)
{
int x = read();
printf("%d\n", searchson(x));
}
}
return 0;
}