求助暴力
查看原帖
求助暴力
526519
Aisaka_Taiga楼主2023/10/15 18:54

思路就是枚举每一个边选还是不选,然后暴力bfs找连通块。

/*
 * @Author: Aisaka_Taiga
 * @Date: 2023-10-15 17:44:43
 * @LastEditTime: 2023-10-15 18:43:59
 * @LastEditors: Aisaka_Taiga
 * @FilePath: \Desktop\T2.cpp
 * The heart is higher than the sky, and life is thinner than paper.
 */
#include <bits/stdc++.h>

#define int long long
#define P 998244353
#define N 1100

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * f;
}

int n, m, a[N], cnt, head[N], b[N], ans, vis[N];
struct node{int u, v, next, ff;}e[N];

inline void add(int u, int v){e[++ cnt] = (node){u, v, head[u], 0}; head[u] = cnt;}

inline int bfs(int s)
{
    int res = 0;
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        res ^= a[u];
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if(vis[v] || e[i].ff) continue;
            q.push(v);
        }
    }
    return res;
}

inline void check()
{
    int res = 1;
    for(int i = 1; i <= n; i ++) vis[i] = 0;
    for(int i = 1; i <= n; i ++)
        if(!vis[i]) res *= bfs(i);
    ans = (ans + res) % P;
    return ;
}

inline void dfs(int x)
{
    if(x == n)
    {
        for(int i = 1; i < n; i ++)
            if(b[i]) e[i * 2 - 1].ff = e[i * 2].ff = 1;
        check();
        for(int i = 1; i < n; i ++)
            if(b[i]) e[i * 2 - 1].ff = e[i * 2].ff = 0;
        return ;
    }
    b[x] = 1;
    dfs(x + 1);
    b[x] = 0;
    dfs(x + 1);
    return ;
}

signed main()
{
    n = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    for(int i = 2; i <= n; i ++)
    {
        int fa = read();
        add(i, fa);
        add(fa, i);
    }
    dfs(1);
    cout << ans << endl;
    return 0;
}
2023/10/15 18:54
加载中...