我不好说，因为考场上我想成二分图然后就gg了
这题不难，真的不难。
∣ T i ∣ ≤ 2 |T_i|\le 2 ∣Ti∣≤2这个性质一看就非常亲切啊，可以看成一条 a i a_i ai到 b i b_i bi的连边，不妨将问题做一些泛化，将 ∣ T i ∣ = 1 |T_i|=1 ∣Ti∣=1看成连向 a i a_i ai的自环。
那么对于一个连通块显然边的数目不超过点的数目，让我们先讨论一些比较简单的情形。
如果基环树且基环为自环，那么选择方式唯一，简单算一下即可。
如果基环树且基环不为自环，那么基环外选择方式唯一，基环内有两种方式，简单贪心一下应该不难得出答案。
如果为树，假设 { a i } \{a_i\} {ai}已经确定了，不妨看成是以 u u u为根并且完成定向的一颗有根树， Bob \text{Bob} Bob可以将 v v v到根节点的路径上的边反向，那么相当于每个点存了一个答案，初始所有点答案都为 0 0 0， Bob \text{Bob} Bob会选择答案最小的那个点。然后 Alice \text{Alice} Alice依次加入每条边，对于没有别固定的边 ( u , v ) (u,v) (u,v)，设 u u u是 v v v的父亲，如果选 v v v相当于 v v v子树外的点答案 + 1 +1 +1，如果选 u u u相当于 v v v子树内的点答案 + 1 +1 +1（称为不动点），如果有两个点 u , v u,v u,v都是翻转点，那么显然 u , v u,v u,v满足祖先关系（否则不优），而显然选深度小的点作为不动点更优，那么就做完了。
复杂度 O ( n log n ) O(n\log n) O(nlogn)。
总之是非常套路的题，但是不知道为啥考场上没想出来。文章来源：https://www.toymoban.com/news/detail-407698.html
总之就是非常难写，今年省选代码量确实有一点点大文章来源地址https://www.toymoban.com/news/detail-407698.html
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define db double
#define fi first
#define se second
using namespace std;
const int N=1e6+5;
int T,n,m,fa[N],sz1[N],sz2[N],a[N][2],b[N][2];
int rt,re,pre[N],prepos[N],visit[N],task,res,dfn[N],num,home[N],cntnode;
int head[N*2],nxt[N*2],to[N*2],pos[N*2],tot;
int posedge;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
struct node{
int dat,min;
}t[N<<2];
void Add(int p,int x){
t[p].min+=x,t[p].dat+=x;
}
void pushup(int p){
t[p].min=min(t[p<<1].min,t[p<<1|1].min);
}
void pushdown(int p){
if(t[p].dat){
Add(p<<1,t[p].dat),Add(p<<1|1,t[p].dat);
t[p].dat=0;
}
}
void upd(int p,int l,int r,int ql,int qr,int x){
if(ql<=l&&r<=qr){
Add(p,x);
return;
}
int mid=l+r>>1;pushdown(p);
if(ql<=mid)upd(p<<1,l,mid,ql,qr,x);
if(mid<qr)upd(p<<1|1,mid+1,r,ql,qr,x);
pushup(p);
}
int qry(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr)return t[p].min;
int mid=l+r>>1;pushdown(p);
if(qr<=mid)return qry(p<<1,l,mid,ql,qr);
if(mid<ql)return qry(p<<1|1,mid+1,r,ql,qr);
return min(qry(p<<1,l,mid,ql,qr),qry(p<<1|1,mid+1,r,ql,qr));
}
void add(int x,int y,int z){
to[++tot]=y,pos[tot]=z,nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,pos[tot]=z,nxt[tot]=head[y],head[y]=tot;
}
void unionset(int x,int y){
int u=find(x),v=find(y);
if(u!=v)fa[u]=v,sz1[v]+=sz1[u]+1,sz2[v]+=sz2[u];
else sz1[v]++;
}
int calc(int pos,int v){
assert(v);
return a[pos][0]==v||a[pos][1]==v;
}
int X,Y,Z;
int check(int pos){
return a[pos][0]==b[pos][0]&&a[pos][1]==b[pos][1]||a[pos][0]==b[pos][1]&&a[pos][1]==b[pos][0];
}
//fixed
void findroot(int u,int topf){
visit[u]=task;
for(int k=head[u];k;k=nxt[k]){
if(k!=(topf^1)){
int v=to[k];
if(visit[v]!=task)findroot(v,k);
else {
rt=u;
if(u==v)posedge=pos[k];
}
}
}
}
//fixed
void dfs(int u,int topf){
visit[u]=task;
for(int k=head[u];k;k=nxt[k]){
int v=to[k];
if(k!=(topf^1)){
if(visit[v]!=task){
pre[v]=u,prepos[v]=pos[k],dfs(v,k);
res+=calc(pos[k],v);
}
else if(u!=rt){
assert(!re);
re=u;
if(check(pos[k])){
Z++;
}
else {
if(calc(pos[k],rt))X++;
else if(calc(pos[k],re))Y++;
}
}
}
}
}
int solve1(int u){
rt=u,re=0,task++;
X=0,Y=0,Z=0,res=0,posedge=0;
findroot(rt,0);
if(posedge)res+=calc(posedge,rt);
task++;
dfs(rt,0);
if(!re)return res;
assert(rt!=re);
while(re!=rt){
int tmp=prepos[re];
res-=calc(tmp,re);
if(check(tmp)){
Z++;
}
else{
if(calc(tmp,re))X++;
else if(calc(tmp,pre[re]))Y++;
}
re=pre[re];
}
if(X>Y)swap(X,Y);
if(X+Z<=Y)return X+Z+res;
return (X+Y+Z)/2+res;
}
void modify(int u,int state,int f){
if(state==0){
upd(1,1,m,dfn[u],dfn[u]+home[u]-1,f);
}
else{
upd(1,1,m,dfn[u],dfn[u]+home[u]-1,-f);
upd(1,1,m,1,cntnode,f);
}
}
void dfs1(int u,int topf){
dfn[u]=++num,home[u]=1,cntnode++;
for(int k=head[u];k;k=nxt[k]){
int v=to[k];
if(v!=topf){
dfs1(v,u),home[u]+=home[v];
}
}
}
void dfs2(int u,int topf,int f){
for(int k=head[u];k;k=nxt[k]){
int v=to[k];
if(v!=topf){
if(check(pos[k])){
modify(v,1,f);
}
else if(calc(pos[k],v)){
modify(v,1,f);
}
else if(calc(pos[k],u)){
modify(v,0,f);
}
dfs2(v,u,f);
}
}
}
void dfs3(int u,int topf){
res=max(res,qry(1,1,m,1,cntnode));
for(int k=head[u];k;k=nxt[k]){
int v=to[k];
if(v!=topf){
if(check(pos[k])){
modify(v,1,-1);
modify(v,0,1);
}
dfs3(v,u);
if(check(pos[k])){
modify(v,1,1);
modify(v,0,-1);
}
}
}
}
int solve2(int u){
num=0,cntnode=0,dfs1(u,0);
assert(cntnode==sz2[find(u)]);
res=0;
dfs2(u,0,1),dfs3(u,0),dfs2(u,0,-1);
assert(t[1].min==0);
return res;
}
int solve(){
int tot=0;
for(int i=1;i<=m;i++){
if(find(i)==i){
if(sz1[i]>sz2[i]){
return -1;
}
if(sz1[i]==sz2[i])tot+=solve1(i);
else tot+=solve2(i);
}
}
return tot;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n>>m;tot=1;for(int i=1;i<=m;i++)head[i]=0;
for(int i=1;i<=m;i++)fa[i]=i,sz1[i]=0,sz2[i]=1;
for(int i=1;i<=n;i++)a[i][0]=a[i][1]=b[i][0]=b[i][1]=0;
for(int i=1;i<=n;i++){
int k;cin>>k;
while(k--)cin>>a[i][k];
}
for(int i=1;i<=n;i++){
int k;cin>>k;
if(k==2){
while(k--)cin>>b[i][k];
unionset(b[i][0],b[i][1]);
add(b[i][0],b[i][1],i);
}
else{
while(k--)cin>>b[i][k];
unionset(b[i][0],b[i][0]);
add(b[i][0],b[i][0],i);
}
}
cout<<solve()<<"\n";
}
}
到了这里，关于【学习笔记】[省选联考 2023] 填数游戏的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
