代码求调(悲)dfs+lca+查分
查看原帖
代码求调(悲)dfs+lca+查分
513005
GuoJZ2010楼主2024/1/28 12:29
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=50100;
const int M=501000;
const int INF=2147483647;
struct Edge{
	int v,nxt;
}edge[N];
int head[N],cnt;
void add(int u,int v){
	edge[++cnt]=(Edge){v,head[u]};
	head[u]=cnt;
}
int n,k,mx;
int fa[N][20],dep[N],d[N];//16
void dfs(int x,int y){
	//cout<<x<<"\n";
	fa[x][0]=y;
	dep[x]=dep[y]+1;
	for(int i=head[x];i;i=edge[i].nxt){
		int t=edge[i].v;
		if(t==fa[x][0]) continue;
		dfs(t,x);
		d[x]+=d[t];
	}
	mx=max(d[x],mx);
//	cout<<x<<" "<<d[x]<<"\n";
}
int quary(int x,int y){
	int lca;
	if(dep[x]<dep[y]) swap(x,y);
	for(int k=16;k>=0;k--){
		if(dep[fa[x][k]]>dep[y]) x=fa[x][k];
	}
	if(x==y) return x;
	for(int k=16;k>=0;k--){
		if(fa[x][k]!=fa[y][k]){
			x=fa[x][k];
			y=fa[y][k];
		}
	}
	return fa[x][0];
}
int main(){
	cin>>n>>k;
	for(int a,b,i=1;i<n;i++){
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	for(int a,b,i=1;i<=k;i++){
		cin>>a>>b;
		int lca=quary(a,b);
		d[a]+=1;
		d[b]+=1;
		d[fa[lca][0]]-=1;
		d[lca]-=1;
	}
	dfs(1,0);
	cout<<mx<<"\n";
	return 0;
}

2024/1/28 12:29
加载中...