Game on a Tree Gym - 102392F(树上最大匹配)

思路:

本质是求一个树上的最大匹配能否覆盖所有的点。

dfs遍历，用qian[]数组记录当前节点的子树内有几个没有匹配的点(初始化为-1因为可以匹配掉一个子树中未匹配的点)，pipei[]数组记录当前节点是否匹配。如果一个点u的子节点有未匹配的，那么u可以匹配掉一个点，但是有多个未匹配的点，就得累积在u上。也就是说如果qian[]数组>0，那么子树中有未匹配的点，需要将该子树的根u标记为未匹配状态，使得u的父亲fu能知道u中有未匹配的点，从而使fu可以匹配。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
vector<int>E[maxn];
bool pipei[maxn];
int qian[maxn];
void dfs(int u,int fu){
    qian[u]=-1;
    int cnt=0;
    for(auto v:E[u]){
        if(v==fu)continue;
        dfs(v,u);
        qian[u]+=max(qian[v],pipei[v]?0:1);
        if(!pipei[v])cnt++;
    }
    if(!cnt||qian[u]>0)pipei[u]=0;
    else pipei[u]=1;
    return;
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1,0);
    if(qian[1]!=0){
        printf("Alice\n");
 
    }
    else printf("Bob\n");
}

Game on a Tree Gym - 102392F(树上最大匹配)

原文：https://www.cnblogs.com/ucprer/p/11795688.html