P3379 LCA模板 警示后人
查看原帖
P3379 LCA模板 警示后人
586455
liyiHuan楼主2022/11/8 16:58

存在 a == b 的询问 如果你是Tarjan算法

那么你保存m次询问询问时应该是

vector<pii> q[N]; 
for (int i=1;i <= m;i ++ )
{
	cin >> u >> v;
	if (u^v) 
	{
		q[u].push_back({v, i});
		q[v].push_back({u, i});
	}
	else ans[i] = u;
}

而不是

for (int i=1;i <= m;i ++ )
{
	cin >> u >> v;
	q[u].push_back({v, i});
	if (u^v) q[v].push_back({u, i});
}
2022/11/8 16:58
加载中...