终于找到了#1的错误原因

刚看到题目时，我尝试在读入树的同时直接将最大深度和最大宽度算出

CPP

for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		if(a[x].le!=0)	a[x].ri=y;//x已经有左节点了就存到右节点 
		else a[x].le=y;//否则存左节点 
		a[y].fa=x;//设置父节点 
		a[y].d=a[x].d+1;//子节点的深度是父节点+1 
		maxd=max(maxd,a[y].d);//找最大深度 
		wide[a[y].d]++;//子节点所在深度所对的宽度+1 
		maxw=max(maxw,wide[a[y].d]);//找最大宽度 
	}

结果第一个点wa了，91分。获得了下方一个讨论版的提示，我意识到题目输入的节点可能不按顺序，即：

CPP

如果照上面的处理方法则会输出深度为2，但画图可知深度为3. 我照着这种规律修改程序，

CPP

for(int i=1;i<=n-1;i++){//一开始输入只存储各自的子节点
		int x,y;
		scanf("%d%d",&x,&y);
		if(a[x].le!=0)	a[x].ri=y;
		else a[x].le=y;
	}
	for(int i=1;i<=n;i++){//从1开始按每个节点分左右子节点进行建树
		if(a[i].le!=0){
			a[a[i].le].fa=i;
			a[a[i].le].d=a[i].d+1;
			maxd=max(maxd,a[a[i].le].d);
			wide[a[a[i].le].d]++;
			maxw=max(maxw,wide[a[a[i].le].d]);
		}
		if(a[i].ri!=0){
			a[a[i].ri].fa=i;
			a[a[i].ri].d=a[i].d+1;
			maxd=max(maxd,a[a[i].le].d);
			wide[a[a[i].ri].d]++;
			maxw=max(maxw,wide[a[a[i].ri].d]);
		}
	}

深度输出为3了，提交发现还是91分，wa第一个点。思索了一段时间，拍出了一些情况，找到了一种可能的出错原因。我在上一个程序输入xy的地方加上了一句：

CPP

if(x>y) cout<<"a";

结果它输出了a！！！！

这下终于破案了。第一个测试点中

存在父节点编号比子节点编号大的情况。

就比如：

CPP

4

1 4
2 3
4 2

1 4

//正确输出：
//4
//1
//1

找到了问题那解决起来就简单了。

在建树的时候选用图的遍历方法，然后再分别判断深度和宽度。或者仍用建树的方法，但需要特殊处理。

终于找到了#1的错误原因

讨论操作

结果它输出了a！！！！

存在父节点编号比子节点编号大的情况。

回复

相关推荐

终于找到了#1的错误原因