求打捞码风
  • 板块灌水区
  • 楼主gw2381
  • 当前回复16
  • 已保存回复16
  • 发布时间2024/8/13 17:03
  • 上次更新2024/8/13 19:49:13
查看原帖
求打捞码风
1279550
gw2381楼主2024/8/13 17:03

大家的码风都是怎么样的呢?

我的码风:

#include<bits/stdc++.h>
using namespace std;
long long N,M,R,P,A[500010],spot1,spot2,heavyson[500010],deep[500010],size[500010],father[500010],top[500010];
vector <long long> son[500010];
void dfs1(long long num)
{
	long long zone=0;
	for(long long i=0;i<son[num].size();i++)
	{
		if(son[num][i]==father[num]) continue;
		deep[son[num][i]]=deep[num]+1;
		father[son[num][i]]=num;
		dfs1(son[num][i]);
		size[num]+=size[son[num][i]];
		if(size[son[num][i]]>zone)
		{
			zone=size[son[num][i]];
			heavyson[num]=son[num][i];
		}
	}
	size[num]++;
}
void dfs2(long long num)
{
    for(long long i=0;i<son[num].size();i++)
    {
        if(son[num][i]==father[num]) continue;
        if(heavyson[num]==son[num][i])
        {
        	top[heavyson[num]]=top[num];
        	dfs2(heavyson[num]);
		}
		else
		{
			top[son[num][i]]=son[num][i];
			dfs2(son[num][i]);
		}
	}
}
long long LCA(long long x,long long y)
{
	if(deep[x]<deep[y])
	{
		swap(x,y);
	}
	while(1)
	{
		if(top[x]==top[y])
	    {
		    return y;
	    }
	    if(deep[top[x]]>deep[top[y]])
	    {
	    	swap(x,y);
		}
		y=father[top[y]];
		if(deep[x]<deep[y]) swap(x,y);
	}
}
int main()
{
	scanf("%lld%lld%lld",&N,&M,&R);
	for(long long i=1;i<N;i++)
	{
		scanf("%lld%lld",&spot1,&spot2);
		son[spot1].push_back(spot2);
		son[spot2].push_back(spot1);
	}
	dfs1(R);
	top[R]=R;
	dfs2(R);
	while(M--)
	{
		scanf("%lld%lld",&spot1,&spot2);
		printf("%lld\n",LCA(spot1,spot2));
	}
} 
2024/8/13 17:03
加载中...