rt,赛时调了许久,dfs 树上节点(会特判是否是父亲,不是父亲才去搜索,猜测可能是初始化问题,但除了 memset 以外的任何初始化都没有任何效果)还 TLE/MLE,但如果给每个点打标记就好了,但是不理解。而且除此之外还 WA,找不到 hack 样例。
#include<bits/stdc++.h>
using namespace std;
//#define int long long
struct st{
int v,ne;
};
struct tree{
int h[1000009];
st sd[2000009];
int inn;
void add(int u,int v){
sd[++inn].v=v;
sd[inn].ne=h[u];
h[u]=inn;
}
int dep[1000009];
int zj[1000009];
int db[1000009];bool v[1000009];
void cl(int t,int fa){
v[t]=0;
zj[t]=db[t]=0;
dep[t]=0;
for(int i=h[t],z;i;z=sd[i].ne,sd[i].ne=0,i=z){
if(sd[i].v!=fa){
cl(sd[i].v,t);
}
sd[i].v=0;
}
h[t]=0;
}
void clear(int m){
/*for(int i=0;i<=m;i++){
dep[i]=zj[i]=db[i]=h[i]=0;
v[i]=0;
//sd[i].v=sd[i].ne=sd[i+m].v=sd[i+m].ne=0;
}
for(int i=0;i<=inn;i++){
sd[i].v=sd[i].ne=0;
}*/
cl(1,0);
inn=0;
}
void dfs(int t,int fa){
//if(v[t]){
// return;
//}
v[t]=1;
zj[t]=db[t]=0;
dep[t]=dep[fa]+1;
for(int i=h[t];i;i=sd[i].ne){
if(sd[i].v!=fa){
dfs(sd[i].v,t);
if(zj[sd[i].v]+1>zj[t]){
db[t]=zj[t];
zj[t]=zj[sd[i].v]+1;
}else if(zj[sd[i].v]+1>db[t]){
db[t]=zj[sd[i].v]+1;
}
}
}
if(db[t]){
db[t]+=zj[t];
}
for(int i=h[t];i;i=sd[i].ne){
if(sd[i].v!=fa){
db[t]=max(db[t],db[sd[i].v]);
}
}
}
int fr(int x,int t,int fa){
//return 0;
if(t==x){
for(int i=h[t];i;i=sd[i].ne){
if(dep[sd[i].v]<dep[x]){
return fr(x,sd[i].v,t)+1;
}
}
return -1e9;
}
int ma;
ma=0;
for(int i=h[t];i;i=sd[i].ne){
if(sd[i].v!=fa){
ma=max(ma,fr(x,sd[i].v,t)+1);
}
}
if(t==1&&ma==0){
//cout<<x<<" "<<t<<" "<<-1e16<<endl;
return -1e9;
}
//cout<<x<<" "<<t<<" "<<ma<<endl;
return ma;
}
int far(int x){
return fr(x,x,0);
}
void mem(){
dep[0]=-1;
dfs(1,0);
}
}a,b,c;
int a1[100009];
int a2[100009];
signed main(){
std::ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int m;
cin>>m;
for(int i=2;i<=m;i++){
int f;
cin>>f;
a.add(f,i);
a.add(i,f);
}
cin>>m;
for(int i=2;i<=m;i++){
int f;
cin>>f;
b.add(f,i);b.add(i,f);
}
for(int i=3;i<=n;i++){
cin>>m;
int ma;
ma=m;
for(int j=2;j<=m;j++){
int f;
cin>>f;
ma=max(ma,f);
c.add(f,i);
c.add(i,f);
}
c.mem();
a1[i-2]=c.zj[1];
a2[i-2]=c.db[1];c.clear(ma);
}
n-=2;
a.mem();
b.mem();
int x,y;
cin>>x>>y;
int s1,s2,d1,d2;
s1=a.dep[x];
s2=max(a.zj[x],a.far(x));
d1=b.dep[y];
d2=max(b.zj[y],b.far(y));
int ans;
ans=-1e9;
int sum;
sum=-1e9;
for(int i=1;i<=n;i++){
if(a2[i]){
for(int i=1;i<=n;i++){
ans+=a1[i];
}
for(int i=1;i<=n;i++){
if(a2[i]){
sum=max(sum,a2[i]-a1[i]);
}
}
ans+=sum;
ans+=s1+d1;
break;
}
}
sum=0;
sum=max(s1+d2,s2+d1);
for(int i=1;i<=n;i++){
sum+=a1[i];
}//cout<<sum<<endl;
ans=max(ans,sum);
cout<<ans+1+n<<endl;
//cout<<s1<<" "<<s2<<" "<<d1<<" "<<d2<<endl;
return 0;
}