风暴之眼

摘要:
背景:通过月岛、蟹王和天体探测器,您成功地结合了三种天体技术。接下来,你需要去暴风眼的中心,为神秘实验的最后一步做准备。风暴中的道路构成了一个具有n个节点的无根树,第i个节点具有初始权重和类型。有两种类型的节点:$type节点和$exttt{OR}$type节点。接下来的n-1行,每行都有两个整数x和y,描述了无根树中的一条边。输出格式每行输出一个整数,表示初始权重和类型的可能组合数。

题目背景

通过月岛,帝王蟹和天体探测仪,你成功拼合了三个天体科技,接下来你要做的,就是来到风暴之眼的中心,准备那个神秘实验的最后一步。

最终的真相近在咫尺,你能否成功通过这场考验呢?

题目描述

天体风暴中的气象瞬息万变。

风暴中的道路构成一棵 n 个结点的无根树,第 i个结点有初始权值 (w_i)(w_i)为 0 或 1)和类型 (t_i)

结点的类型分为两种:( exttt{AND})$ 型结点和$ exttt{OR}$ 型结点。

(对于 exttt{AND} 型结点,每一秒结束后它的权值将变为它与它所有邻居上一秒权值的 exttt{AND} 和)

(对于 exttt{OR} 型结点,每一秒结束后它的权值将变为它与它所有邻居上一秒权值的 exttt{OR} 和)

现在,已知从某一时刻起,所有结点的权值都不再发生任何变化,将此时点 i 的权值称为 (a_i)

现不知每个点的初始权值和类型,只知道最终每个点的权值 (a_i),求出有多少种可能的初始权值和类型的组合,答案对 998244353 取模。

输入格式

第一行,一个整数 n,表示树的结点数。

第二行,n 个整数 (a_1, a_2, ldots , a_n),表示每个结点最终的权值。

接下来 n-1 行,每行两个整数 x,y,描述无根树中的一条边。

输出格式

输出一行一个整数,表示可能的初始权值和类型的组合数量。

输入输出样例

输入 #1复制

2
0 0
1 2

输出 #1复制

6

说明/提示

【样例 1 解释】

有如下六种初始权值和类型的组合:

  1. (((w_1, t_1), (w_2, t_2)) = ((0, exttt{AND}), (0, exttt{AND})))
  2. (((w_1, t_1), (w_2, t_2)) = ((0, exttt{AND}), (0, exttt{OR})))
  3. (((w_1, t_1), (w_2, t_2)) = ((0, exttt{OR}), (0, exttt{AND})))
  4. (((w_1, t_1), (w_2, t_2)) = ((0, exttt{OR}), (0, exttt{OR})))
  5. (((w_1, t_1), (w_2, t_2)) = ((1, exttt{AND}), (0, exttt{AND})))
  6. (((w_1, t_1), (w_2, t_2)) = ((0, exttt{AND}), (1, exttt{AND})))

【数据范围】

本题采用捆绑测试。

对于 100% 的数据,$$2 le n le 2 imes {10}^5,1 le x, y le n,a_i in { 0, 1 }$$,保证输入构成一棵树。

子任务编号(nleq)特殊限制
110
220
31000
4({10}^5)y=x+1
5({10}^5)(a_i=0)
6(2 imes {10}^5)

题目分析

首先是:OR节点变为1则停止变化,AND节点变为0则停止变化

然后是变化结果的条件:

1.and 点组成的连通块,当且仅当初始时连通块内部全是 1,与其相邻的一圈 or 点初值也全是 1的时候,最终会全变为 1;否则最终会全变为 0

2.or 点组成的连通块,当且仅当初始时连通块内部全是 0,与其相邻的一圈 and 点初值也全是 0的时候,最终会全变为 0;否则最终会全变为 1

考虑到树上的联通块条件,进行树形DP,令(f[i][j][k][t])表示(i)节点,类型(j),初始化值设为(k)(t)是否满足条件以上变化条件

注意:DP转移时需要考虑一些特殊情况,比如 (x)作为 (y) 的父亲满足了$ y$的限制

具体的转移分析见注释

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
struct Node
{
    int next,to;
}edge[400005];
int head[200005],num=0;
int n,a[200005],Mod=998244353;
/**
 * 第2维0表示and,1表示or
 * 第3维表示初始值
 * 第4维表示是否符合and/or联通块条件
 * **/
int f[200005][2][2][2];
void add(int u,int v){
    num++;
    edge[num].next=head[u];
    head[u]=num;
    edge[num].to=v;
}
void dfs(int x,int fa){
    if (a[x]==0) {
        f[x][0][0][1]=1;
        f[x][0][1][0]=1;
        f[x][1][0][1]=1;
    }else{
        f[x][1][1][1]=1;
        f[x][1][0][0]=1;
        f[x][0][1][1]=1;
    }
    for (int i=head[x];i;i=edge[i].next){
        int v=edge[i].to;
        if (v==fa) continue;
        dfs(v,x);
        int temp[2][2][2]={0};
        if (a[x]==0&&a[v]==0){
            //and连通块,x和邻居至少一个0
            for (int v1=0;v1<2;v1++)
                for (int j=0;j<2;j++)
                    for (int v2=0;v2<2;v2++)
                        for (int k=0;k<2;k++){
                            temp[0][v1][j|k]+=1ll*f[x][0][v1][j]*f[v][0][v2][k]%Mod;
                            temp[0][v1][j|k]%=Mod;
                        }
            //x是and节点,v是or节点,都是0(要考虑父节点对子节点条件约束)
            temp[0][0][1]+=1ll*f[x][0][0][1]*f[v][1][0][1]%Mod;
            temp[0][0][1]%=Mod;
            //or连通块,全部是0
            //x是or节点,v是and,都是0(要考虑父节点对子节点条件约束)
            temp[1][0][1]+=(1ll*f[x][1][0][1]*f[v][1][0][1]%Mod+1ll*f[x][1][0][1]*f[v][0][0][1]%Mod)%Mod;
            temp[1][0][1]%=Mod;
        }
         if (a[x]==0&&a[v]==1){
            //x是and节点,v是or节点
            for (int v1=0;v1<2;v1++)
                for (int j=0;j<2;j++)
                    for (int v2=0;v2<2;v2++)
                        for (int k=0;k<2;k++)
                        if (k||v1){
                            temp[0][v1][j|(!v2)]+=1ll*f[x][0][v1][j]*f[v][1][v2][k]%Mod;
                            temp[0][v1][j|(!v2)]%=Mod;
                        }
        }
        if (a[x]==1&&a[v]==0){
            //x是or节点,v是and节点
            for (int v1=0;v1<2;v1++)
                for (int j=0;j<2;j++)
                    for (int v2=0;v2<2;v2++)
                        for (int k=0;k<2;k++)
                        if (k||(!v1)){
                            temp[1][v1][j|v2]+=1ll*f[x][1][v1][j]*f[v][0][v2][k]%Mod;
                            temp[1][v1][j|v2]%=Mod;
                        }
        }
        if (a[x]==1&&a[v]==1){
            //or连通块,x和邻居至少一个1
            for (int v1=0;v1<2;v1++)
                for (int j=0;j<2;j++)
                    for (int v2=0;v2<2;v2++)
                        for (int k=0;k<2;k++){
                            temp[1][v1][j|k]+=1ll*f[x][1][v1][j]*f[v][1][v2][k]%Mod;
                            temp[1][v1][j|k]%=Mod;
                        }
            //x是or节点,v是and节点,都是1(要考虑父节点对子节点条件约束)
            temp[1][1][1]+=1ll*f[x][1][1][1]*f[v][0][1][1]%Mod;
            temp[1][1][1]%=Mod;
            //and连通块,全部是0
            //x是and节点,v是or,都是1(要考虑父节点对子节点条件约束)
            temp[0][1][1]+=(1ll*f[x][0][1][1]*f[v][0][1][1]%Mod+1ll*f[x][0][1][1]*f[v][1][1][1]%Mod)%Mod;
            temp[0][1][1]%=Mod;
        }
        memcpy(f[x],temp,sizeof(temp));
    }
}
int main(){
    int u,v;
    ll ans;
    cin>>n;
    for (int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=0;i<n-1;i++){
        scanf("%d%d",&u,&v);
        add(u,v);add(v,u);
    }
    dfs(1,0);
    ans=((f[1][0][0][1]+f[1][0][1][1])%Mod+(f[1][1][0][1]+f[1][1][1][1])%Mod)%Mod;
    cout<<ans;
}

免责声明:文章转载自《风暴之眼》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇浏览器缓存原理【转】RAID基本知识下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

oracle查询连接数、并发数、共享池大小

1、查看当前数据库建立的会话情况:selectsid,serial#,username,program,machine,statusfromv$session;2、查询数据库当前进程的连接数:selectcount(*)fromv$process;3、查看数据库当前会话的连接数:selectcount(*)fromv$session;4、查看数据库的并发连接...

POI设置边框

对单元格设置边框时,有上下左右位置之分,所以POI也准备了四个不同的方法。值说明BORDER_DASH_DOTdash-dotborderBORDER_DASH_DOT_DOTdash-dot-dotborderBORDER_DASHEDdashborderBORDER_DOTTEDdotborderhair-lineborderBORDER_DOUBLEd...

AirtestIDE基本功能(二)

文件菜单-相应工具栏上的前四个按钮:新建、打开、保存和另存为新。单击此按钮以选择是否使用创建脚本。air后缀或带有的脚本。py后缀。新脚本将初始化代码,以帮助您从API引入Airtest的各种接口,并自动初始化设备。你可以看到。air脚本文件实际上是一个公用文件夹,其中放置了通过IDE捕获的图像和运行日志。软件关闭时,布局信息将自动保存。(3) 选项-设置设...

Python之路

Python之路引子与其感慨路难行,不如马上出发PythonPython之路(一):初识Python之路(二):基本数据类型(上)Python之路(三):基本数据类型(下)Python之路(四):函数介绍及使用Python之路(五):内置函数Python之路(六):迭代器,装饰器,生成器Python之路(七):字符串处理Python之路(八):基础模块(一)...

WPF绑定功能常用属性介绍

这是实质上是System.Windows.Data.BindingMode.OneWay绑定的一种简化形式,它在源值不更改的情况下提供更好的性能。确定依赖属性绑定在默认情况下是单向还是双向的编程方法是:使用System.Windows.DependencyProperty.GetMetadata获取属性的属性元数据,然后检查System.Windows.Fr...

WPF 制作圆角按钮

在程序对应坐置插入以下代码,或是先拖一个按钮控件到窗体中,再替换对应的代码。...