暴力法,只想得部分分,但是两个超时,请指教
查看原帖
暴力法,只想得部分分,但是两个超时,请指教
285961
魏老师楼主2025/1/25 09:26
//树上的查询 暴力法 
#include<bits/stdc++.h>
using namespace std;
int tree[510][510],deep[510],father[510],book[510];		
int n,p,q,k;
void f(int r)
{
	for(int i=1;i<=n;i++)
	{
		if(tree[r][i]!=0&&book[i]==0)  
		{
			deep[i]=deep[r]+1;
			father[i]=r;
			book[i]=1;
			f(i);
		}
	}
}

int lca(int x,int y)
{
	if(deep[x]<deep[y]) swap(x,y); 
	while(deep[x]>deep[y]) x=father[x];
	while(x!=y)
	{
		x=father[x];
		y=father[y];
	}
	return x;
}
int main()
{
	int a,b;
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		cin>>a>>b;
		tree[a][b]=1;
		tree[b][a]=1;
	}
	deep[1]=1;book[1]=1;
	f(1);
	/*测试代码 
	for(int i=1;i<=n;i++)
		cout<<deep[i]<<" ";
	*/
	int n1,maxn=0;
	cin>>n1;
	while(n1--)
	{
		cin>>p>>q>>k;
		maxn=0;
	    for(int i=p;i<=q;i++)
	    {
	    	if(k==1)
			{
				for(int o1=p;o1<=q;o1++)
				{
					maxn=max(maxn,deep[o1]);
				}
			}
			else 
				for(int o1=i;o1<=i+k-2;o1++)
				{
					for(int o2=o1+1;o2<=i+k-1;o2++)
					{
							maxn=max(maxn,deep[lca(o1,o2)]);
					}
				}
		}
		cout<<maxn<<endl; 
	}
	
	return 0;
}

2025/1/25 09:26
加载中...