由于全是赋值操作，我们容易发现每个值最终状态所依赖的都是某个确定的状态（\(T\)、\(F\)、\(U\)），或者是某个位置的初始值。于是先 \(O(m)\) 预处理每个 \(x_i\) 的最终状态来源 \(p_i\)，即 \(x_i\) 的值依赖于 \(x_{p_i}\)，以及它们的关系 \(r_i\)，\(0\) 表示相等，\(1\) 表示取反。
考虑图论建模，无向边 \((i,p_i)\) 表示 \(i\) 和 \(p_i\) 是取反的关系。
如果 \(r_i=0\) 就并查集缩这两个点（为了保持图中的边全是取反意义），取反则连无向边。特别的，如果 \(i\) 的值依赖一个确定的值，建三个特殊点 \(T\)、\(F\)、\(U\) 连单向边向 \(i\)，表示支配关系，答案计入 \(U\) 支配的联通块中点数，和不被任何一个特殊点支配的、且存在奇环的联通块中的点数。
可能的疑问
- 为什么是奇环？
若联通块中存在奇环，根据我们这个图的边的定义，它一定会得出自己是自己的取反这种显然错误的结论。
- 为什么不用管 \(T\)、\(F\) 中的联通块？
联通块里所有的点的状态都会被他们的源点——特殊点所确定，题目保证方案存在，所以不用管这里是不是有冲突。
code
#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=1e5+10;
int c,t,n,m,ans;
int p[MAXN],r[MAXN];
int fa[MAXN];
set<int> g[MAXN];
bool vised[MAXN];
int dep[MAXN],cnt[MAXN];
inline int find(int x){if(fa[x]==x){return x;}return fa[x]=find(fa[x]);
}
void merge(int x,int y){int fx=find(x);int fy=find(y);if(fx!=fy){fa[fy]=fx;cnt[fx]+=cnt[fy];}
}
pair<int,int> dfs(int x){pair<int,int> res(0,cnt[x]);vised[x]=true;for(int v:g[x]){if(vised[v]){if(((dep[x]-dep[v])&1)==0){res.first=1;}}else{dep[v]=dep[x]+1;auto [f,w]=dfs(v);res.first|=f;res.second+=w;}}return res;
}
signed main(){//freopen("P9869_3.in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>c>>t;while(t--){cin>>n>>m;ans=0;for(int i=1;i<=n+3;++i){p[i]=i;r[i]=0;fa[i]=i;vised[i]=false;cnt[i]=1;g[i].clear();dep[i]=0;}for(int i=1;i<=m;++i){char c;int u,v;cin>>c;if(c=='-'){cin>>u>>v;p[u]=p[v];r[u]=r[v]^1;}else if(c=='+'){cin>>u>>v;p[u]=p[v];r[u]=r[v];}else if(c=='T'){cin>>u;p[u]=n+1;r[u]=0;}else if(c=='F'){cin>>u;p[u]=n+2;r[u]=0;}else{cin>>u;p[u]=n+3;r[u]=0;}}for(int i=1;i<=n;++i){if(!r[i]&&p[i]<=n){merge(i,p[i]);}}for(int i=1;i<=n;++i){if(p[i]>n){g[p[i]].emplace(find(i));continue;}if(r[i]){g[find(i)].emplace(find(p[i]));g[find(p[i])].emplace(find(i));}}ans+=dfs(n+3).second-1;dfs(n+2);dfs(n+1);for(int i=1;i<=n;++i){if(vised[find(i)]) continue;auto [f,w]=dfs(find(i));ans+=f*w;}cout<<ans<<endl;}return 0;
}