植树方案[fake_2-SAT]

本文主要是介绍植树方案[fake_2-SAT]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

类似的奇偶约数问题,可以转化为图论来解决

本题有2-SAT的味道,又有二分图染色的味道

总之通过将束缚转化为图,求图中连通块的个数

每个连通块有两种"染色"方案,根只有一种,答案就是2^(cnt-1)

---

#include<bits/stdc++.h>
#define N 100005
#define M N*2
#define LL long long
using namespace std;
int first[N],next[M],to[M],w[M],tot;
int n,q,id[N],flag,cnt; LL ans=1;
void add(int x,int y,int z){next[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;
}
void dfs(int u){if(flag) return;if(id[u]==-1) id[u]=0;for(int i=first[u];i;i=next[i]){int t=to[i];if(id[t]==-1){if(w[i]==0) id[t]=id[u];else id[t]=id[u]^1;dfs(t);}else{if(id[t]==id[u] && w[i]==1) {flag=1; return;}if(id[t]!=id[u] && w[i]==0) {flag=1; return;}}}
}
int main(){scanf("%d%d",&n,&q);for(int i=1;i<n;i++){int x,y; scanf("%d%d",&x,&y);}for(int i=1;i<=q;i++){int x,y,z; scanf("%d%d%d",&x,&y,&z);add(x,y,z),add(y,x,z);}memset(id,-1,sizeof(id));for(int i=1;i<=n;i++)if(id[i]==-1){dfs(i); if(flag) {printf("0"); return 0;}else cnt++;}for(int i=1;i<cnt;i++) ans=(LL)(ans*2)%998244353;printf("%d",ans); return 0;
}

 

这篇关于植树方案[fake_2-SAT]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---