为何只有13分?
查看原帖
为何只有13分?
223392
Belarus楼主2020/10/29 11:13

感觉思路没什么问题,树上差分 cx,cyc_x,c_y 自加1,clca,cfalcac_{lca},c_{fa_{lca}} 自减1
难道是LCA写错了吗

#include<bits/stdc++.h>
using namespace std;
const int sze=2e5+10;
int n,k,t,ans=0;
int tot=0,ver[sze],head[sze],nxt[sze];
int f[sze][25],d[sze];
int c[sze],son[sze];
queue<int> q;
inline void add(int x,int y){
	ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
inline void bfs(){
	q.push(1);d[1]=1;
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=head[x];i;i=nxt[i]){
			int y=ver[i];
			if(d[y]) continue;
			d[y]=d[x]+1;
			f[y][0]=x;
			for(int j=1;j<=t;++j) f[y][j]=f[f[y][j-1]][j-1];
			q.push(y);
		}
	}
}
inline int LCA(int x,int y){
	if(d[x]>d[y]) swap(x,y);
	for(int i=t;i>=0;--i) if(d[f[y][i]]>=d[x]) y=f[y][i];
	if(x==y) return x;
	for(int i=t;i>=0;--i) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[x][i];
	return f[x][0];
}
void dfs(int x){
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(d[y]!=d[x]+1) continue;
		dfs(y);
		c[x]+=c[y];
	}
	ans=max(ans,c[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k;
	t=(int)(log(n)/log(2))+1;
	for(int i=1;i<=n-1;++i){
		int x,y;
		cin>>x>>y;
		add(x,y),add(y,x);
	}
	bfs();
	while(k--){
		int x,y;
		cin>>x>>y;
		c[x]++;c[y]++;
		int tmp=LCA(x,y);
		c[tmp]--;
		c[f[tmp][0]]--;
	}
	dfs(1);
	cout<<ans<<'\n';
	return 0;
}
2020/10/29 11:13
加载中...