RT,上洛谷ide提示是“超出内存限制”......
代码看了十几遍了,似乎不会爆栈,数组也不会
#include<cstdio>
//#include<vector>
using namespace std;
struct node
{
int d=1,l=0,r=0,p;
}tree[120];
int n;
int maxd;
int wide[120];//用于判最大宽度
bool pd[120];//用于判断tarjan算法中是否已遍历过某节点
int j[120];//并查集
int find(int x)
{
if(x!=j[x])j[x]=find(x);
return j[x];
}
void _union(int x,int y)
{
j[find(x)]=find(y);
}
int xgoal1,xgoal2;//分别为题目中的最后两个输入
void tarjan(int x)
{
if(flag==1)return;//已找到目标节点就直接返回
if(tree[x].l)tarjan(tree[x].l);//递归左右子树
if(tree[x].r)tarjan(tree[x].r);
pd[x]=1;//已走过
// if(pd[tree[x].l]==1&&pd[tree[x].r]==1)
// {
// if(x==1)return;
if((x==xgoal2&&pd[xgoal1]==1) || (x==xgoal1&&pd[xgoal2]==1))//若已走到目标节点(此时当前节点的左右子树都递归完毕)
{
flag=1;
printf("%d", (tree[find(xgoal1)].d - tree[xgoal1].d) * 2 + tree[xgoal2].d - tree[find(xgoal1)].d);//输出
return;
}
// }
if(x!=1)_union(x,tree[x].p);//合并
}
int main()
{
pd[0]=1;
wide[1]=1;
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int a,b;
scanf("%d %d",&a,&b);
if(tree[a].l) tree[a].r=b;
else tree[a].l=b;
tree[b].p=a;
if(tree[b].d <= tree[a].d) tree[b].d = tree[a].d + 1;
else tree[a].d=tree[b].d+1;
wide[tree[b].d]++;
if(tree[a].d>maxd)maxd=tree[a].d;
if(tree[b].d>maxd)maxd=tree[b].d;
}
for(int i=1;i<=n;i++)j[i]=i;
int maxw=0;
for(int i=1;i<=100;i++)
{
if(wide[i]>maxw)maxw=wide[i];
}
// printf("%d %d\n",tree[a].d,tree[b].d);
printf("%d\n%d\n",maxd,maxw);
// printf("-------%d %d--------\n",tree[1].l,tree[1].r);
scanf("%d %d",&xgoal1,&xgoal2);
tarjan(1);
return 0;
}
求大佬指教!QwQ