ST表+LCA,自建测试样例全部通过6分
查看原帖
ST表+LCA,自建测试样例全部通过6分
741418
gameserver楼主2024/5/31 09:10

自建测试样例全部通过,但是只有6分,实在找不到哪里有问题,谁来帮我看看

#include<bits/stdc++.h>
using namespace std;
vector<int> a[50005];
int n,k,u,v,dfn[50005],st[20][50005],d=1,c[50005],ans=0;
void dfs1(int fa,int ch){	//构建DFN表
	st[0][d]=fa;
	dfn[ch]=d++;
	for(int i=0;i<a[ch].size();i++)
		if(fa!=a[ch][i])dfs1(ch,a[ch][i]);
}
void build(){		//构建ST表
	int len=log2(n);
	for(int i=1;i<=len;i++)
		for(int j=1;j<=n-(1<<i)+1;j++)
			if(dfn[st[i-1][j]]<dfn[st[i-1][j+(1<<i-1)]])
				st[i][j]=st[i-1][j];
			else st[i][j]=st[i-1][j+(1<<i-1)];
//	for(int i=0;i<=len;i++){
//		for(int j=1;j<=n-(1<<i)+1;j++)
//			cout<<st[i][j]<<" ";
//		cout<<endl;
//	}
}
int query(int u,int v){		//ST表查LCA
	if(u==v)return v;	//区间起点终点相同
	u=dfn[u],v=dfn[v];
	if(u>v)swap(u,v);
	int len=log2(v-u++);
	return min(st[len][u],st[len][v-(1<<len)+1]);
}
void dfs2(int fa,int ch){		//最后查询,返回子节点的差分数组权重,加到整个回溯路径
	for(int i=0;i<a[ch].size();i++){
		if(fa==a[ch][i])continue;
		dfs2(ch,a[ch][i]);
		c[ch]+=c[a[ch][i]];
	}
	ans=max(ans,c[ch]);
}
int main(){
	freopen("P3128_2.in","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	dfs1(0,1);
//	for(int i=1;i<=n;i++)cout<<dfn[i]<<" ";
//	cout<<endl;
//	for(int i=1;i<=n;i++)cout<<st[0][i]<<" ";
	build();
	//cout<<query(4,6);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&u,&v);
		c[u]++,c[v]++;
		int lca=query(u,v);
		//cout<<lca<<endl;
		c[lca]--;		//LCA被重复计算,需要减一
		c[st[0][dfn[lca]]]--;	//LCA父节点减一
	}
//	for(int i=1;i<=n;i++)cout<<c[i]<<" ";
//	cout<<endl;
	dfs2(0,1);
	cout<<ans<<endl; 
	//for(int i=1;i<=n;i++)cout<<c[i]<<" ";
	return 0;
}
2024/5/31 09:10
加载中...