【AT2307】Tree Game

这个题居然还算今天讲的简单的,我觉得我今年SDOI凉了啊qwq
考虑这么一个事情,对于一个点x和他的子树,这个点先手必胜,一定存在一个儿子son,使得a_{x}>a_{son}并且son这个子树先手必败。
假如a_{x} \leq a_{son},那么后手就可以通过不停回到x然后耗死先手,而a_{x}>a_{son}时候,后手如果跳回x则会被耗死,所以他只能往son这个子树跳,进入这个子树,先后手交换,原来的后手变成了先手,这个时候先手必败,也就说原来的后手必败。
边界条件是跳到叶子节点,这个时候没有任何一个点可以供这个点上的先手跳,为先手必败态。
每次考虑一个点的时候dfs一遍 ,时间复杂度O(n^2)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

typedef unsigned int uint;

template<typename inp_typ>

inline void re(inp_typ &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

bool sta[5050];

int tot = -1, lx, ly, head[5050], n, a[5050];

struct in
{
    int to, ne;
}ter[10010];

inline void build(int f, int l)
{
    ter[++ tot] = (in){l, head[f]}, head[f] = tot;
    ter[++ tot] = (in){f, head[l]}, head[l] = tot;
}

void dfs(int no, int f)
{
    sta[no] = 0;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == f)
            continue;
        dfs(to, no);
        if(a[no] > a[to] && (!sta[to]))
        {
            sta[no] = 1; break;
        }
    }
}

int main()
{
    re(n), memset(head, -1, sizeof(head));
    for(ri i = 1; i <= n; re(a[i ++]));
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), build(lx, ly);
    for(ri i = 1; i <= n; i ++)
    {
        dfs(i, 0);
        if(sta[i])
            printf("%d ", i);
    }
    system("pause");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注