```cpp
inline void ADDson(ll x, ll k)
{
ADD(1, 1, n, seg[x], seg[x] + siz[x] - 1, k);
}
inline ll querySon(ll x)
{
return query(1, 1, n, seg[x], seg[x] + siz[x] - 1);
}
inline void ADDRange(ll x, ll y, ll k)
{
while (top[x] != top[y]) //当两个节点不在同一条重路径上
{
if (deep[x] < deep[y])
swap(x, y); //处理更深的x点
ADD(1, 1, n, seg[top[x]], seg[x], k);
x = fa[top[x]]; //*important
}
if (deep[x] > deep[y])
swap(x, y); //找到更浅的x点
// printf("add %d and %d\n", x, y);
ADD(1, 1, n, seg[x], seg[y], k);
}
inline ll queryRange(ll x, ll y)
{
ll ans = 0;
while (top[x] != top[y])
{
if (deep[x] < deep[y])
swap(x, y); //处理更深的x点往上跳
ans = (ans + query(1, 1, n, seg[top[x]], seg[x])) % mod;
x = fa[top[x]]; //*important
}
if (deep[x] > deep[y])
swap(x, y); //找到更浅的x点
ans = (ans + query(1, 1, n, seg[x], seg[y])) % mod;
return ans;
}
int main()
{
n = read(), m = read(), r = read(), mod = read();
for (register ll i = 1; i <= n; ++i)
w[i] = read() % mod;
for (register ll i = 1; i < n; ++i)
addedge(read(), read());
dfs1(r, 0, 1);
dfs2(r, r); //一棵预处理完的树
build(1, 1, tot);
while (m--)
{
ll op = read();
if (op == 1)
{
ll x = read(), y = read(), z = read() % mod;
ADDRange(x, y, z);
}
else if (op == 2)
{
ll x = read(), y = read();
printf("%lld\n", queryRange(x, y));
}
else if (op == 3)
{
ll x = read(), y = read();
ADDson(x, y);
}
else
{
ll x = read();
printf("%lld\n", querySon(x));
}
}
return 0;
}
```
内容过长qwq
by 渺小的Mastar @ 2019-05-26 07:51:36
~~的确不会~~
by 7KByte @ 2019-05-26 08:00:03
@[渺小的Mastar](/space/show?uid=140659)
```
while (top[x] != top[y])
{
if (deep[x] < deep[y])
swap(x, y);
ans = (ans + query(1, 1, n, seg[top[x]], seg[x])) % mod;
x = fa[top[x]];
}
```
改成
```
while (top[x] != top[y])
{
if (deep[top[x]] < deep[top[y]])
swap(x, y);
ans = (ans + query(1, 1, n, seg[top[x]], seg[x])) % mod;
x = fa[top[x]];
}
```
by 7KByte @ 2019-05-26 08:02:11
@[Gang_Leader](/space/show?uid=119261) 太神了，雪中送炭啊！Orz
by 渺小的Mastar @ 2019-05-26 08:07:55
@[Gang_Leader](/space/show?uid=119261) 三个M怎么办..qwq
by 渺小的Mastar @ 2019-05-26 08:09:39
%%%%%%%%
by 渺小的Mastar @ 2019-05-26 08:09:56
@[Gang_Leader](/space/show?uid=119261) 呜呜呜呜5555555555
by 渺小的Mastar @ 2019-05-26 08:11:57
@[Gang_Leader](/space/show?uid=119261) 蒟蒻紧紧的抱紧大佬的大腿
by 渺小的Mastar @ 2019-05-26 08:12:48
我是蒟蒻……
MAXN开大一倍试试
by 7KByte @ 2019-05-26 08:14:01
双向边要两倍空间
by 7KByte @ 2019-05-26 08:15:07