bzoj 3722: PA2014 Final Budowa game theory

meaning of the title

Mr. Fancy announced that the XJOI group would elect the next group leader. There are two candidates, XYW and Gilly.
A total of n people (numbered from 1 to n) participated in the voting. A tree structure is formed between them, and the root node (node 1) is Fancy. The nodes on the tree have two identities: Expert (leaf node) or leader (non leaf node). Each expert has his own choice - support one of XYW and gilly; each leader has several subordinates (son nodes), and the choice of leader depends on the party with more subordinates, and the number of subordinates is guaranteed to be odd, so there will be no draw. Finally, Fancy's choice is the result of the election.
Gilly and XYW know that there are still some experts who are in a state of hesitation and can get his support as long as they go to lobby. However, due to lack of energy, each person can only choose to lobby one expert every day; XYW gets up earlier, and he lobbies before Jili. The two men alternate until each expert has a certain choice. Does XYW have a strategy to win the election?


Maybe I've done a lot of big game problems recently, but I didn't think it was such a violent solution.
To judge who will win, just look at the number of trees that will win.
As for the output scheme... Direct violence enumeration and judgment are ok.


using namespace std;

const int N=1005;

int n,a[N],ans[N],col[N],cnt,last[N];
struct edge{int to,next;}e[N];

int read()
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;

void addedge(int u,int v)

int dfs(int x)
    if (a[x]<=0) return col[x];
    int s=0;
    for (int i=last[x];i;i=e[i].next) s+=dfs(e[i].to);
    if (s<0) return -1;
    if (s>0) return 1;
    return 0;

int main()
    for (int i=1;i<=n;i++)
        if (a[i]<0) col[i]=a[i]==-1?-1:1;
        else for (int x,j=1;j<=a[i];j++) x=read(),addedge(i,x);
    if (dfs(1)==-1) {puts("NIE");return 0;}
    int tot=0;
    for (int i=1;i<=n;i++)
        if (!a[i])
            if (dfs(1)) ans[++tot]=i;
    printf("TAK %d\n",tot);
    for (int i=1;i<tot;i++) printf("%d ",ans[i]);
    if (tot) printf("%d",ans[tot]);
    return 0;

Added by jokerofsouls on Thu, 14 May 2020 18:29:11 +0300