首先,如果一个边双$e-dcc$中含有一条标记边,那么这个边双里面所有的点都可以得到泡芙。
那么这道题就非常显然了,利用tarjan求出无向图中所有的$e-dcc$ 缩点,对于每一个缩点后的点记录前缀点权和和前缀边权和。
一个图上的路径就可以对应到图中的缩点之后的生成树上面的一条树的路径,用前缀和维护这条路径上有泡芙的个数即可。
只要点上或者边上有救可以,所以我们只需要求一个lca,然后用预处理出的前缀点权和和前缀边权和来求解。
```cpp
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=3e5+10;
struct rec{ int pre,to,w;}a[N<<1];
struct edge{ int u,v,w;};
vector<edge>E;
stack<int>s;
int dfn[N],low[N],c[N],val[N][2],g[N][22],dep[N],head[N];
int n,m,tot=1,cnt;
bool bridge[N<<1];
void adde(int u,int v,int w)
{
a[++tot].pre=head[u];
a[tot].to=v;
a[tot].w=w;
head[u]=tot;
}
void tarjan(int u,int e)
{
dfn[u]=low[u]=++dfn[0];
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to;
if (!dfn[v]) {
tarjan(v,i); low[u]=min(low[u],low[v]);
if (low[v]>dfn[u]) bridge[i]=bridge[i^1]=1;
} else if (i!=(e^1)) low[u]=min(low[u],dfn[v]);
}
}
void draw(int u,int col)
{
c[u]=col;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to; if (bridge[i]||c[v]) continue;
draw(v,col);
}
}
void dfs(int u,int fa)
{
g[u][0]=fa; dep[u]=dep[fa]+1;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to; if (v==fa) continue;
val[v][0]+=val[u][0];
val[v][1]=val[u][1]+a[i].w;
dfs(v,u);
}
}
void init()
{
for (int i=1;i<=21;i++)
for (int j=1;j<=cnt;j++)
g[j][i]=g[g[j][i-1]][i-1];
}
int lca(int u,int v)
{
if (dep[u]<dep[v]) swap(u,v);
for (int i=21;i>=0;i--)
if (dep[g[u][i]]>=dep[v]) u=g[u][i];
if (u==v) return u;
for (int i=21;i>=0;i--)
if (g[u][i]!=g[v][i]) u=g[u][i],v=g[v][i];
return g[u][0];
}
signed main()
{
scanf("%lld%lld",&n,&m);
for (int i=1;i<=m;i++) {
int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
adde(u,v,0); adde(v,u,0);
E.push_back((edge){u,v,w});
}
for (int i=1;i<=n;i++) if (!dfn[i]) tarjan(i,0);
for (int i=1;i<=n;i++) if (!c[i]) draw(i,++cnt);
tot=0; memset(head,0,sizeof(head)); memset(a,0,sizeof(a));
for (int i=0;i<(int)E.size();i++) {
int u=E[i].u,v=E[i].v,w=E[i].w;
if (c[u]==c[v]) { if (w) val[c[u]][0]=1; continue;}
adde(c[u],c[v],w); adde(c[v],c[u],w);
}
dfs(1,0); init();
int Q; scanf("%lld",&Q);
while (Q--) {
int u,v; scanf("%lld%lld",&u,&v);
int l=lca(c[u],c[v]);
int ret0=val[c[u]][0]+val[c[v]][0]-val[g[l][0]][0]-val[l][0];
int ret1=val[c[u]][1]+val[c[v]][1]-2*val[l][1];
if (ret0 || ret1) puts("YES"); else puts("NO");
}
return 0;
}
```