LCA+树上差分66pts(是我太菜了吗)
查看原帖
LCA+树上差分66pts(是我太菜了吗)
305891
Eraine楼主2022/5/29 09:43

rt,检查过很多遍,LCALCA 应该是没有错误,是细节错误吗?

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=5e4;
const int K=20;
int num[N+5],tot;
struct node{
	int end;
	int nxt;
	void add(int u,int v){
		end=v;
		nxt=num[u];
		num[u]=tot;
	}
}edge[2*N+5];
int f[N+5][K+5];
int d[N+5];
int n,k;
bool vis[N+5];
void dfs1(int x,int dep){//遍历找父节点
	d[x]=dep;
	for(int i=num[x];i;i=edge[i].nxt){
		int y=edge[i].end;
		if(!d[y]){
			f[y][0]=x;
			dfs1(y,dep+1);
		}
	}
}
void build(){//建立倍增表
	k=log(n)+1;
	for(int j=1;j<=k;j++)
		for(int i=1;i<=n;i++)
			f[i][j]=f[f[i][j-1]][j-1];
}
int query(int x,int y){//LCA查询
	if(d[x]>d[y])
		swap(x,y);
	for(int i=k;i>=0;i--)
		if(d[f[y][i]]>=d[x])
			y=f[y][i];
	if(x==y)
		return x;
	for(int i=k;i>=0;i--)
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	return f[x][0];
}
int S[N+5];
void dfs2(int x){//树上差分
	vis[x]=true;
	for(int i=num[x];i;i=edge[i].nxt){
		int y=edge[i].end;
		if(!vis[y]){
			dfs2(y);
			S[x]+=S[y];
		}
	}
}
int main(){
	int m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		edge[++tot].add(u,v);
		edge[++tot].add(v,u);
	}
	dfs1(1,1);
	build();
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		S[u]++;
		S[v]++;
		S[query(u,v)]--;
		S[f[query(u,v)][0]]--;
	}
	dfs2(1);
	int ans=0;
	for(int i=1;i<=n;i++)
		ans=max(ans,S[i]);
	printf("%d\n",ans);
	return 0;
}
2022/5/29 09:43
加载中...