0分求助
  • 板块P10406 Company
  • 楼主sbno333
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/3 21:54
  • 上次更新2024/5/4 08:57:09
查看原帖
0分求助
416975
sbno333楼主2024/5/3 21:54

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;
}
2024/5/3 21:54
加载中...