P3384 MnZn求救 -> 为什么dfs2无限递归?
查看原帖
P3384 MnZn求救 -> 为什么dfs2无限递归?
308107
Xu__楼主2021/2/22 21:35

代码如下,为何 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

2021/2/22 21:35
加载中...