题解 P2416 【泡芙】

这道题首先需要跑一遍边双连通分量，然后剩下来的就是一颗树，每个点有其点权，询问对于树上一条 \((u,v)\) 的简单路径，时候经过的点的点权和不为 \(0\)。

其他题解基本都是跑 \(LCA\)，去求路径的权值，其实这并没有必要，因为两点间的路径点权和为 \(0\) 的是一个连通块，若询问的 \(2\) 点在同一个连通块里就说明它们之间路径的点权和为 \(0\)，求连通块可用并查集做，若想得到完美的 \(O(n)\) 解，则可以 \(bfs\)。

并查集

#include
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<=(b);--i)
using namespace std;
inline int read(){char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int N=3e5+10;
int n,m,cnt,dfn[N],low[N],sccnum[N],sk[N],tot,scccnt,sccval[N],fa[N];
vector >v[N];
vectorscctree[N];
void dfs(int x,int fa){
	low[x]=dfn[x]=++cnt;
	sk[tot++]=x;
	for(pairi:v[x])
		if(!dfn[i.fi]){
			dfs(i.fi,x);
			low[x]=min(low[x],low[i.fi]);
		}else if(i.fi!=fa){
			low[x]=min(low[x],dfn[i.fi]);
		}
	if(low[x]==dfn[x]){
		scccnt++;
		do{
			sccnum[sk[--tot]]=scccnt;
		}while(sk[tot]!=x);
	}
}
inline int find(int x){
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
int main(){
	n=read(),m=read();
	F(i,1,m){
		int x=read(),y=read(),z=read();
		v[x].pb(mp(y,z));
		v[y].pb(mp(x,z));
	}
	dfs(1,0);
	F(i,1,n)
		for(pairj:v[i])
			if(sccnum[i]==sccnum[j.fi])sccval[sccnum[i]]+=j.se;
			else if(!j.se)scctree[sccnum[i]].pb(sccnum[j.fi]);
	F(i,1,scccnt)fa[i]=i;
	F(i,1,scccnt){
	    int l=find(i);
		if(!sccval[i])
			for(int j:scctree[i])
				if(!sccval[j])
					fa[find(j)]=l;
	}
	int q=read();while(q--){
		int s=read(),t=read();
		if(sccval[sccnum[s]]||sccval[sccnum[t]])puts("YES");
		else if(find(sccnum[s])==find(sccnum[t]))puts("NO");
			else puts("YES");
	}
}

\(bfs\)

#include
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<=(b);--i)
using namespace std;
inline int read(){char ch=getchar(); int w=1,c=0;
	for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
	for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
	return w*c;
}
const int N=3e5+10;
int n,m,cnt,dfn[N],low[N],sccnum[N],sk[N],tot,scccnt,sccval[N],block[N];
vector >v[N];
vectorscctree[N];
void dfs(int x,int fa){
	low[x]=dfn[x]=++cnt;
	sk[tot++]=x;
	for(pairi:v[x])
		if(!dfn[i.fi]){
			dfs(i.fi,x);
			low[x]=min(low[x],low[i.fi]);
		}else if(i.fi!=fa){
			low[x]=min(low[x],dfn[i.fi]);
		}
	if(low[x]==dfn[x]){
		scccnt++;
		do{
			sccnum[sk[--tot]]=scccnt;
		}while(sk[tot]!=x);
	}
}
queueq;
int main(){
	n=read(),m=read();
	F(i,1,m){
		int x=read(),y=read(),z=read();
		v[x].pb(mp(y,z));
		v[y].pb(mp(x,z));
	}
	dfs(1,0);
	F(i,1,n)
		for(pairj:v[i])
			if(sccnum[i]==sccnum[j.fi])sccval[sccnum[i]]+=j.se;
			else if(!j.se)scctree[sccnum[i]].pb(sccnum[j.fi]);
	F(i,1,scccnt)
		if(!block[i]&&!sccval[i]){
			block[i]=i;
			q.push(i);
			while(q.size()){
				int x=q.front();q.pop();
				for(int j:scctree[x])
					if(!block[j]&&!sccval[j]){
						block[j]=i;
						q.push(j);
					}
			}
		}
	int q=read();while(q--){
		int s=read(),t=read();
		if(!block[sccnum[s]]||!block[sccnum[t]])puts("YES");
		else if(block[sccnum[s]]==block[sccnum[t]])puts("NO");
			else puts("YES");
	}
}

卡常的最优解就不放了