代码如下,为何 23~33 行 dfs2 函数无限递归?另外为何使用 Dev-C++ 的调试功能无法显示第 29 行的 v 变量的值?
#include<stdio.h>
#include<iostream>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
const LL N = 1e6 + 16;
LL n, m, p, r, num[N], w[N], son[N], cnt, fa[N], head[N], next[N], ver[N], tot, dep[N], top[N], tpos[N], pre[N], lazy[N], sum[N];
void add(LL x, LL y){ ver[++tot] = y; next[tot] = head[x]; head[x] = tot; }
void dfs1(LL u, LL f)
{
num[u] = 1;
for (LL i = head[u]; i; i = next[i])
{
LL v = ver[i];
if (v == f) continue;
dep[v] = dep[u] + 1; fa[v] = u;
dfs1(v, u);
num[u] += num[v];
if (num[v] > num[son[u]]) son[u] = v;
}
}
void dfs2(LL u, LL tp)
{
top[u] = tp; tpos[u] = ++cnt; pre[cnt] = u;
if (son[u]) dfs2(son[u], tp);
for (LL i = head[u]; i; i = next[u])
{
LL v = ver[i];
if (v == fa[u] && v == son[u]) continue;
dfs2(v, v);
}
}
void Up(LL rt){ sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; }
void Down(LL rt, LL llen, LL rlen)
{
if(lazy[rt])
{
lazy[rt << 1] = (lazy[rt << 1] % p + lazy[rt] % p) % p; lazy[rt << 1 | 1] = (lazy[rt << 1 | 1] % p + lazy[rt] % p) % p;
sum[rt << 1] = (sum[rt << 1] % p + ((lazy[rt] % p) * (llen % p)) % p) % p; sum[rt << 1 | 1] = (sum[rt << 1 | 1] % p + ((lazy[rt] % p) * (rlen % p)) % p) % p;
lazy[rt] = 0;
}
}
void build(LL l, LL r, LL rt)
{
if (l == r)
{
sum[rt] = w[tpos[l]] %p;
return;
}
LL m = (l + r) >> 1;
build(lson);build(rson);
Up(rt);
}
LL query(LL l, LL r, LL rt, LL nowl, LL nowr)
{
if (nowl <= l && nowr >= r) return sum[rt];
LL m = (l + r) >> 1, ans = 0;
Down(rt, m - l + 1, r - m);
if (nowl <= m) ans = (ans % p + query(lson, nowl, nowr) % p) % p;
if (nowr > m) ans = (ans % p + query(rson, nowl, nowr) % p) % p;
Up(rt);
return ans % p;
}
void modify(LL l, LL r, LL rt, LL nowl, LL nowr, LL k)
{
if (nowl <= l && nowr >=r)
{
sum[rt] = (sum[rt] % p + (((r - l + 1) % p) * k) % p) % p;lazy[rt] = (lazy[rt] % p + k % p) % p;
return ;
}
LL m = (l + r) >> 1;
Down(rt, m - l + 1, r - m);
if (nowl <= m) modify(lson, nowl, nowr, k);
if (nowr > m) modify(rson, nowl, nowr, k);
Up(rt);
}
LL chain_query(LL u, LL v)
{
LL ans = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
ans = (ans % p + query(1, n, 1, tpos[top[u]], tpos[u]) % p) % p;
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
ans = (ans % p + query(1, n, 1, tpos[u], tpos[v]) % p) % p;
return ans % p;
}
LL chain_modify(LL u, LL v, LL k)
{
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
modify(1, n, 1, tpos[top[u]], tpos[u], k);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
modify(1, n, 1, tpos[u], tpos[v], k);
}
int main()
{
cin>>n>>m>>r>>p;
for (LL i = 1; i <= n; i++) cin>>w[i];
for (LL i = 1, x, y; i <= n - 1; i++) cin>>x>>y,add(x, y),add(y, x);
dfs1(r, 0);
dfs2(r, r);
build(1, n, 1);
for (LL i = 1, bo, x, y, z; i <= m; i++)
{
cin>>bo;
switch (bo)
{
case 1: cin>>x>>y>>z; chain_modify(x, y, z); break;
case 2: cin>>x>>y; cout<<chain_query(x, y)<<endl; break;
case 3: cin>>x>>z; modify(1, n, 1, tpos[x], tpos[x] + num[x] - 1, z); break;
case 4: cin>>x; cout<<query(1, n, 1, tpos[x], tpos[x] + num[x] - 1)<<endl; break;
}
}
return 0;
}
谢谢各位轻松A掉这道题的大佬帮忙awa