#12 WA求调(带注释+WA记录)
  • 板块P10406 Company
  • 楼主Zhenghw
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/3 22:40
  • 上次更新2024/5/4 09:36:58
查看原帖
#12 WA求调(带注释+WA记录)
1201196
Zhenghw楼主2024/5/3 22:40

都是按照题解的想法做的,真看不出来哪里还有问题

#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;
}

WA记录

2024/5/3 22:40
加载中...