比赛 ?板子大赛 评测结果 WWTTTTTTTT
题目名称 消防演练 最终得分 0
用户昵称 2_16鸡扒拌面 运行时间 8.962 s
代码语言 C++ 内存使用 343.26 MiB
提交时间 2026-01-17 11:10:55
显示代码纯文本
#include <bits/stdc++.h>
#define N 500010
#define jyt 18
using namespace std;

int n;
vector<int> g[N];           
int zxy[N];                 
int kew[N];                   
int depth[N];               
long long sum[N];                 
int father[N][jyt]; 

void DFS(int u,int fa)
{
	depth[u]=depth[fa]+1;
	sum[u] = sum[fa]+kew[u];
	father[u][0]=fa;
	for(int j=1;j<jyt;j++) {
		if (father[u][j-1]!=0)
			father[u][j]=father[father[u][j-1]][j-1];
		else
			father[u][j]=0;
	}
	for(int v=0;v<g[u].size();v++) 
    {
		if (v==fa) continue;
		DFS(v,u);
	}
}

int LCA(int x, int y) {
	if (depth[x]<depth[y])
		swap(x,y); 
	for (int j=jyt-1;j>=0;j--) 
    {
		if (father[x][j]>0&&depth[father[x][j]]>=depth[y]) x=father[x][j];
		if (x==y) return x;
	}
	for (int j=jyt-1;j>=0;j--) 
    {
		if (father[x][j]!=father[y][j])
        {
			x=father[x][j];
			y=father[y][j];
		}
	}
	return father[x][0];
}

int main() {
	freopen("drill.in", "r", stdin);
	freopen("drill.out", "w", stdout);
    cin>>n;
	for (int i=1;i<=n;i++) 
    {
		g[i].clear();
		zxy[i] = 0; 
	}
	for (int i=1; i < n; i++) {
		int x,y;
		cin>>x>>y;
		g[x].push_back(y); 
		g[y].push_back(x);
		zxy[x]++;
		zxy[y]++;
	}
	for (int i=1;i<=n;i++) {
		kew[i]=zxy[i]-2;
	}
	depth[0]=-1;
	sum[0]=0;
	DFS(1,0);
	long long ans=-0x3f3f3f3f;
	for (int u=1;u<=n;u++)
    {
		for (int v=u+1;v<=n;v++) 
        {
			int lca=LCA(u,v);
			long long path_sum=sum[u]+sum[v]-2*sum[lca]+kew[lca];
			ans=max(ans,path_sum);
		}
	}
	cout<<ans+2;
	return 0;
}