2023“钉耙编程”中国大学生算法设计超级联赛（1）（已更新1012 ）-526互联

1012
题意：有一棵树，可以把任意一个点作为根节点，每次A,B两个人操作，B先手，选择除了根节点外的节点，减去以他为根节点的树，谁最后不能操作，统计A不能操作的次数，答案为cnt/n
思路：先把问题简化，成以1为根结点，判断时候胜利，既然每次都是操作子孙节点，那么考虑用异或和（xor），
对于根节点u，子节点为\(v_1,v_2...v_l\)
\(SG(u)=SG(v_1)xorSG(v_2)xor...SG(v_l)\)
如果SG(u)>0则这点先手能走向胜利，SG(u)==0，表示，无论先手怎么选后手都能选择相同的，则后手胜利，反之先手胜利。
经过第一遍dfs后，可以确定点1的SG(1)函数，
利用换根dp，再跑一遍dfs即可求得，其余点的SG函数，原理，两次异或等价于没有异或
代码：

点击查看代码

#include <bits/stdc++.h>

#define Max 200005

using namespace std;

const int mod=1e9+7;

struct Edge{
    int v,to;
}e[Max*2];

int T,n,sz,head[Max],f1[Max],f2[Max];
//f1表示以1为根节点，每个节点的子节点的异或值
//f2就是SG函数

inline int qpow(int x,int y){ //快速幂
    int ans=1;
    while(y){
        if(y&1)ans=1ll*ans*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return ans;
}

inline void add(int u,int v){ //邻接表，建树
    e[++sz].v=v;e[sz].to=head[u];head[u]=sz;
}

inline void dfs1(int u,int fa){ //深搜1
    int now=0;
    for(int i=head[u];i;i=e[i].to){
        int v=e[i].v;
        if(v==fa)continue;
        dfs1(v,u);
    //    cout<<f1[v]<<" "<<u<<" "<<now<<"dsa\n";
        now^=(f1[v]+1);
        
    }
    f1[u]=now;
    return;
}

inline void dfs2(int u,int fa){ //深搜2
    for(int i=head[u];i;i=e[i].to){
        int v=e[i].v;
        if(v==fa)continue;
        f2[v]=f1[v]^((f2[u]^(f1[v]+1))+1); //换根
        dfs2(v,u);
    }
    return;
}

int main(){
	// freopen("data2.in","r",stdin);
	// freopen("data2.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<n;i++){
            int u,v;
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs1(1,1);//以1为根节点
        f2[1]=f1[1];
        dfs2(1,1); //换根dp
        int cnt=0;
        for(int i=1;i<=n;i++){ //统计点数
            if(f2[i])cnt++;
        }
      //  cout<<cnt<<'\n';
        cout<<1ll*cnt*qpow(n,mod-2)%mod<<'\n';
        for(int i=1;i<=n;i++)head[i]=0; //初始化
        sz=0;
    }
    return 0;
}

钉耙