求助!P10725 最远点对,不知道我的写法/思路有什么问题,求教
  • 板块题目总版
  • 楼主DGFLSzfd
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/11 17:27
  • 上次更新2024/7/11 19:08:55
查看原帖
求助!P10725 最远点对,不知道我的写法/思路有什么问题,求教
981551
DGFLSzfd楼主2024/7/11 17:27

我的思路想法与该题解类似:题解:P10725 [GESP202406 八级] 最远点对

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;

int n,ans=0; 
bool a[N+10],b[N+10];
vector<int>s[N]; 
int dp[N+10][4];

void dfs(int k)
{
	
	for(int i=0;i<s[k].size();i++)
	{
		int son=s[k][i];
		if(b[son]) continue;
		
		b[son]=1;
		
		dfs(son);
		int w0=0,v0=0,w1=0,v1=0;
		//w0存在k节点的子树中,离他第二远的黑节点的长度
		//w1存在k节点的子树中,离他第二远的白节点的长度
		//v0存离他第二远的黑节点的长度由哪个对于k的子树中来的
		//v0存离他第二远的白节点的长度由哪个对于k的子树中来的
		
		if((dp[son][0]+1>=dp[k][0]) and (a[son]==1 or dp[son][0]>0 ) )
		{
			w1=dp[k][0];  v1=dp[k][1];//找到更长的距离后将第二长的数据换成原先第一长的数据 
			dp[k][0]=dp[son][0]+1;//dp[k][0]存在k节点的子树中,离他第二远的黑节点的长度
			dp[k][1]=s[k][i];//dp[k][1]存离他第二远的白节点的长度由哪个对于k的子树中来的
		}
		if((dp[son][2]+1>=dp[k][2]) and (a[son]==0 or dp[son][2]>0 ) )
		{
			w0=dp[k][2];  v0=dp[k][3];
			dp[k][2]=dp[son][2]+1;
			dp[k][3]=s[k][i];
		}//与上同理 
		if(a[k]==1)ans=max(ans,dp[k][2]); 
		else ans=max(ans,dp[k][0]); //当作为链的情况下 
		
		//以下为什么要判断不等于0,我的想法是他能算答案的前提是它得有找到至少一对黑白点 
		if(dp[k][1]!=dp[k][3] and dp[k][1]!=0 and dp[k][3]!=0) 
		{
			ans=max(ans,dp[k][0]+dp[k][2]);
		}
		if(dp[k][1]!=v0 and v0!=0 and dp[k][1]!=0)
		{
			ans=max(ans,dp[k][0]+w0);
		}
		if(v1!=dp[k][3] and v1!=0 and dp[k][3]!=0)
		{
			ans=max(ans,dp[k][2]+w1);//cout<<"?";
		}
		if(v1!=v0 and v1!=0 and v0!=0 )
		{
			ans=max(ans,w1+w0);
		}//以上为尝试各种不同组合找最优解
		 
//		cout<<dp[k][1]<<' '<<dp[k][3]<<' '<<v1<<' '<<v0<<endl;
//		cout<<dp[k][0]<<' '<<dp[k][2]<<' '<<w1<<' '<<w0<<' '<<ans<<endl;
//		cout<<"------------\n";
	//	cout<<dp[k][0]<<' '<<dp[k][2]<<' '<<ans<<' '<<dp[k][1]<<' '<<dp[k][3]<<endl;
	}
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v;
		s[u].push_back(v);
		s[v].push_back(u);
	}
	b[1]=1;
	dfs(1);
	
	cout<<ans;
}

以上是我的代码,恳请各位大佬指出错误

2024/7/11 17:27
加载中...