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(树上最大匹配)

最新文章

热门文章