都是按照题解的想法做的,真看不出来哪里还有问题
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+5,M=2e6+5;
int i,j,k,n,m,c,h,cnt,ans,maxx,data[2][M];
int d[N],p[M],nx[M],tot[N],head[N],pos[2];
inline void add(const int u,const int v){
tot[u]++,p[++cnt]=v;
nx[cnt]=head[u],head[u]=cnt;
}void dfs(const int u,const int f){
int i,v;
for(i=head[u];i;i=nx[i]){
if((v=p[i])==f)
continue;
d[v]=d[u]+1;
//下面的判断是:如果下一个节点为叶子结点,并且到该节点的距离大于最长路
if(tot[v]==1&&d[v]>d[c])
//更新最长路
c=v;
dfs(v,u);
}
}//更新u节点到所有节点的距离,然后c表示离u节点最远的叶子结点,如果没有的话那么执行完函数后c还是u
int main(){
scanf("%d",&n);
for(i=0;i<2;i++){
scanf("%d",&m);
data[i][1]=m;
for(j=2;j<=m;j++)
scanf("%d",data[i]+j);
}//先存下前两棵树
for(i=2;i<n;i++){
scanf("%d",&m);
for(j=2;j<=m;j++){
scanf("%d",&k);
add(j,k),add(k,j);
}//建树
d[c=1]=0,dfs(1,0);
ans+=h=d[c];
//获取树的高度,此时c为离根最远的叶子结点
d[c]=0,dfs(c,0);
maxx=max(maxx,d[c]-h);
//如题解所述,获取最大的ai-bi
for(j=1;j<=m;j++)
tot[j]=head[j]=0;
}scanf("%d%d",pos,pos+1);
//接下来处理前两棵树,思路基本同上
for(i=0;i<2;i++){
m=data[i][1];
for(j=2;j<=m;j++){
add(j,data[i][j]);
add(data[i][j],j);
}d[c=1]=0,dfs(1,0);
//唯一不同的地方,距离算的是根节点到myz或ljs的距离
ans+=h=d[c=pos[i]];
d[c]=0,dfs(c,0);
maxx=max(maxx,d[c]-h);
for(j=1;j<=m;j++)
tot[j]=head[j]=0;
}printf("%d",n+ans+maxx-1);
return 0;
}