2022 年牛客多校第九场 C 题题解

C Global Positioning System

题意：给定 $nn$ 个点 $mm$ 条边的图，图上每条边有一向量。现在这些边上的向量恰好有一个错误的，原始的图上任意环上向量和为 $\vec{0}\backslash vec\; 0$，找出有多少个可能错误的边。$n,m\le 1\times 10^{5}n,m\; \backslash leq\; 1\backslash times\; 10^5$。

解法：首先找到任意一个生成森林，考虑非树边的加入会对答案造成什么影响：

1. 当前边 $(u,v)(u,v)$ 的加入不会造成冲突。那么对于链 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)u\; \backslash to\; \{\backslash rm\; lca\}(u,v)$ 与 $v\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)v\; \backslash to\; \{\backslash rm\; lca\}(u,\; v)$ 均不能出现错误。
2. 当前边 $(u,v)(u,v)$ 的加入导致了错误。则有以下两种子情况：树边错误与 $(u,v)(u,v)$ 错误。在树上对 $u\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)u\; \backslash to\; \{\backslash rm\; lca\}(u,v)$ 与 $v\to \mathrm{l}\mathrm{c}\mathrm{a}(u,v)v\; \backslash to\; \{\backslash rm\; lca\}(u,\; v)$ 链打标记，记录错误次数。同时 $(u,v)(u,v)$ 边也打上标记，表示可能错误。

最后统计答案的时候，找到所有错误的边的交集，对于树边必然是这些答案中的一个（注意要去掉不允许出错的正确环）。若只有一条非树边的加入导致了错误，则当前错误非树边也可能是错误的。

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=5e5+3;
struct poi{
	LL x,y,z;
	poi operator+(const poi &a) const{
	return (poi){x+a.x,y+a.y,z+a.z};}
	poi operator-(const poi &a) const{
	return (poi){x-a.x,y-a.y,z-a.z};}
	poi operator*(const int k) const{
	return (poi){x*k,y*k,z*k};}
	IL int chk(){return !x&&!y&&!z;}
}dis[N];
struct hh{
	int to,nxt,id;poi w;
}e[N<<1];
struct line{
	int x,y,id;poi w;
}l[N],re[N];
int n,m,num,cnt,fir[N],fa[N][22],vis[N],f[N],dep[N],val[N],id[N],bo[N],ban[N];
vector<line>er;vector<int>ans;
IL int in(){
  char c;int f=1;
  while((c=getchar())<'0'||c>'9')
    if(c=='-') f=-1;
  int x=c-'0';
  while((c=getchar())>='0'&&c<='9')
    x=x*10+c-'0';
  return x*f;
}
IL void add(int x,int y,int pos,poi w){
	e[++num]=(hh){y,fir[x],pos,w},fir[x]=num;
	e[++num]=(hh){x,fir[y],pos,w*-1},fir[y]=num;
}
int find(int x){return x^f[x]?f[x]=find(f[x]):x;}
void dfs1(int u,int f){
	vis[u]=1,dep[u]=dep[f]+1,fa[u][0]=f;
	for(int i=0;fa[u][i];++i)
	  fa[u][i+1]=fa[fa[u][i]][i];
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) dis[v]=dis[u]+e[i].w,dfs1(v,u);
}
IL int Lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;~i;--i)
	  if(dep[fa[x][i]]>=dep[y])
	    x=fa[x][i];
	if(x==y) return x;
	for(int i=19;~i;--i)
	  if(fa[x][i]^fa[y][i])
	    x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
void chk(line l,int pos){
	int x=l.x,y=l.y;
	poi sum=l.w+(dis[y]*-1)+dis[x];
	if(!sum.chk()){
		int lca=Lca(x,y);
		++val[x],++val[y],val[lca]-=2;
		er.push_back(l);
	}
	else bo[pos]=1;
}
IL void print(){
	sort(ans.begin(),ans.end());
	int nn=0;
	for(int i=0;i<ans.size();++i)
	  if(!ban[ans[i]]) ++nn;
	printf("%d\n",nn);
	for(int i=0;i<ans.size();++i)
	  if(!ban[ans[i]]) printf("%d ",ans[i]);
	putchar('\n');
}
void dfs2(int u,int f){
	vis[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) id[v]=e[i].id,dfs2(v,u),val[u]+=val[v];
	if(!val[u]&&id[u]) ans.push_back(id[u]); 
}
void work1(){
	for(int i=1;i<=cnt;++i){
		int x=re[i].x,y=re[i].y,lca=Lca(x,y);
		++val[x],++val[y],val[lca]-=2;
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs2(i,0); 
	print();
}
void dfs3(int u,int f){
	vis[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) id[v]=e[i].id,dfs3(v,u),val[u]+=val[v];
	if(val[u]==er.size()) ans.push_back(id[u]);
}
void dfs4(int u,int f){
	vis[u]=1;
	for(int i=fir[u],v;v=e[i].to;i=e[i].nxt)
	  if(v^f) id[v]=e[i].id,dfs4(v,u),val[u]+=val[v];
	if(val[u]) ban[id[u]]=1;
}
void work2(){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs3(i,0);
	if(er.size()==1) ans.push_back(er[0].id);
	memset(val,0,sizeof(val));
	for(int i=1;i<=cnt;++i)
	  if(bo[i]){
	  	int x=re[i].x,y=re[i].y,lca=Lca(x,y);
	  	++val[x],++val[y],val[lca]-=2;
	  }
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs4(i,0);
	print();
}
void solve(){
	int u,v,x,y,z;
	n=in(),m=in();
	for(int i=1;i<=n;++i) f[i]=i;
	for(int i=1;i<=m;++i)
	  u=in(),v=in(),x=in(),y=in(),z=in(),
	  l[i]=(line){u,v,i,(poi){x,y,z}};
	for(int i=1;i<=m;++i){
		int x=l[i].x,y=l[i].y;
		if(find(x)^find(y)) f[find(x)]=find(y),add(x,y,l[i].id,l[i].w);
		else re[++cnt]=l[i];
	}
	for(int i=1;i<=n;++i)
	  if(!vis[i]) dfs1(i,0);
	for(int i=1;i<=cnt;++i) chk(re[i],i);
	if(!er.size()) work1();
	else work2();
}
int main()
{
	int T=1;
	while(T--) solve();
  return 0;
}