stO afq_pzq Orz(
by Mysterious_Mini @ 2021-11-03 18:01:38
@[pzq_loves_qwq](/user/384214) 帮您改了一下,改的有点多,不好说具体改了哪里,您自己对比一下吧
修改后的 code :
```cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
typedef long long ll;
const ll N = 1e5 + 5;
ll MOD;
struct node
{
ll l, r, sum, lazy;
};
struct segtree
{
node tree[N << 2];
#define u tree[i]
#define lc tree[i << 1]
#define rc tree[i << 1 | 1]
#define len(x) (x.r - x.l + 1 )
inline void pushup(ll i)
{
u.sum = lc.sum + rc.sum;
u.sum %= MOD;
}
inline void pushdown(ll i)
{
lc.sum += len(lc) * u.lazy; lc.sum %= MOD;
lc.lazy += u.lazy; lc.lazy %= MOD;
rc.sum += len(rc) * u.lazy; rc.sum %= MOD;
rc.lazy += u.lazy; rc.lazy %= MOD;
u.lazy = 0;
}
inline void build(ll a[], ll i, ll l, ll r)
{
u.l = l, u.r = r, u.lazy = 0;
if (len(u) == 1)
{
u.sum = a[l] % MOD;
return;
}
ll mid = (l + r) >> 1;
build(a, i << 1, l, mid);
build(a, i << 1 | 1, mid + 1, r);
pushup(i);
}
inline ll query(ll i, ll l, ll r)
{
if (l <= u.l && r >= u.r)
return u.sum;
int ret = 0;
pushdown(i);
ll mid = (u.l + u.r) >> 1;
if (l <= mid)
(ret += query(i << 1, l, r)) %= MOD;
if (r > mid)
(ret += query(i << 1 | 1, l, r)) %= MOD;
return ret;
}
inline void modify(ll i, ll l, ll r, ll k)
{
if (l <= u.l && r >= u.r)
{
u.lazy += k, u.sum += len(u) * k;
u.lazy %= MOD, u.sum %= MOD;
return;
}
pushdown(i);
ll mid = (u.l + u.r) >> 1;
if (l <= mid)
modify(i << 1, l, r, k);
if (r > mid)
modify(i << 1 | 1, l, r, k);
pushup(i);
}
#undef u
#undef lc
#undef rc
#undef len
}
QwQ;
struct edge
{
ll u, v, next;
}
e[2 * N]; ll cnt, head[N];
inline void add_edge(ll u, ll v)
{
e[cnt].u = u, e[cnt].v = v, e[cnt].next = head[u];
head[u] = cnt++;
}
ll father[N], depth[N], size[N], hson[N];
ll top[N], dfn[N], rank[N], dfscnt;
ll init[N];
void dfs1(ll u, ll f)
{
father[u] = f;
depth[u] = depth[f] + 1;
size[u] = 1;
ll qwq = 0;
for (int i = head[u]; ~i; i = e[i].next)
if (e[i].v != f)
{
ll v = e[i].v;
dfs1(v, u);
size[u] += size[v];
if (size[v] > qwq)
qwq = size[v], hson[u] = v;
}
}
void dfs2(ll u, ll a) // a 为链顶
{
top[u] = a;
dfn[u] = ++dfscnt;
rank[dfscnt] = init[u];
if(!hson[u]) return ;
dfs2(hson[u], a);
for (int i = head[u]; ~i; i = e[i].next)
if (e[i].v != father[u] && e[i].v != hson[u])
dfs2(e[i].v, e[i].v);
}
inline ll chain_query(ll u, ll v)
{
ll ans = 0;
while (top[u] != top[v])
{
if (depth[top[u]] < depth[top[v]])
std::swap(u, v);
ans += QwQ.query(1, dfn[top[u]], dfn[u] ); ans %= MOD;
u = father[top[u]];
}
if(depth[u] > depth[v]) std::swap(u, v);
ans += QwQ.query(1, dfn[u], dfn[v]); ans %= MOD;
return ans;
}
inline void chain_modify(ll u, ll v, ll k)
{
while (top[u] != top[v])
{
if (depth[top[u]] < depth[top[v]])
std::swap(u, v);
QwQ.modify(1, dfn[top[u]], dfn[u], k);
u = father[top[u]];
}
if(depth[u] > depth[v]) std::swap(u, v);
QwQ.modify(1, dfn[u], dfn[v], k); ;
}
inline ll subtree_query(ll u)
{
return QwQ.query(1, dfn[u], dfn[u] + size[u] - 1);
}
inline void subtree_modify(ll u, ll k)
{
QwQ.modify(1, dfn[u], dfn[u] + size[u] - 1, k);
}
int main()
{
memset(head, -1, sizeof head);
ll n, q, rt;
scanf("%lld %lld %lld %lld", &n, &q, &rt, &MOD);
for (int i = 1; i <= n; i++)
scanf("%lld", &init[i]);
for (int i = 0; i < n - 1; i++)
{
ll u, v;
scanf("%lld %lld", &u, &v);
add_edge(u, v), add_edge(v, u);
}
dfs1(rt, 0);
dfs2(rt, rt);
QwQ.build(rank, 1, 1, n );
while (q--)
{
ll op, x, y, k;
scanf("%lld", &op);
if (op == 1)
{
scanf("%lld %lld %lld", &x, &y, &k);
chain_modify(x, y, k);
}
if (op == 2)
{
scanf("%lld %lld", &x, &y);
printf("%lld\n", chain_query(x, y));
}
if (op == 3)
{
scanf("%lld %lld", &x, &k);
subtree_modify(x, k);
}
if (op == 4)
{
scanf("%lld", &x);
printf("%lld\n", subtree_query(x));
}
}
return 0;
}
```
by _outcast_ @ 2021-11-03 19:00:39
@[_outcast_](/user/376125) 蟹蟹
by esquigybcu @ 2021-11-03 19:04:23