树上差分和LCA20分求助
查看原帖
树上差分和LCA20分求助
394167
Cure_Wing楼主2022/11/17 22:58
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using std::cin;using std::cout;
constexpr int N=50010;
int n,k,x,y,dep[N],fa[N][20],f[N],Ans;
std::vector<int>edge[N];
inline void dfs(int u,int dad){
	dep[u]=dep[dad]+1;
	fa[u][0]=dad;
	for(int i=0;i<18;++i)
		fa[u][i+1]=fa[fa[u][i]][i];
	for(auto i:edge[u]){
		if(i==dad) continue;
		dfs(i,u);
	}
}
inline int LCA(int x,int y){
	if(dep[x]<dep[y]) std::swap(x,y);
	for(int i=19;i>=0;--i){
		if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		if(x==y) return x;
	}
	for(int i=19;i>=0;--i)
		if(dep[fa[x][i]]&&dep[fa[y][i]]&&dep[fa[x][i]]!=dep[fa[y][i]]){
			x=fa[x][i];
			y=fa[y][i];
		}
	return fa[x][0];
}
inline void ans(int u,int dad){
//	cout<<u<<std::endl;
	for(auto i:edge[u])
		if(i!=dad){
			ans(i,u);
			f[u]+=f[i];
		}
	Ans=std::max(f[u],Ans);
}
signed main(){
 	freopen("P3128_2.in","r",stdin);
// 	freopen("xx.out","w",stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	cin>>n>>k;
	for(int i=1;i<n;++i){
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(1,0);
	for(int i=1;i<=k;++i){
		cin>>x>>y;
		++f[x];++f[y];
		int t=LCA(x,y);
		--f[t];--f[fa[t][0]];
	}
	ans(1,0);
//	for(int i=1;i<=n;++i) cout<<f[i]<<' ';cout<<'\n';
	cout<<Ans;
    return 0;
}
2022/11/17 22:58
加载中...