找树

题目描述

定义 \otimes_1, \otimes_2, \otimes_31,2,3 分别为按位与、按位或、按位异或运算。记 a_iai 表示 aa 的从低位到高位的第 ii 个二进制位。定义一个作用在 ww 位二进制数上的新运算 \oplus,满足对于结果 a\oplus bab 的每一位 (a\oplus b)_i(ab)i(a\oplus b)_i = a_i \otimes_{o_i} b_i(ab)i=aioibi。不难验证 \oplus 运算满足结合律和交换律。

给出一张 nn 个点 mm 条边的无向图,每一条边的权值是一个 ww 位二进制数(即小于 2^w2w 的非负整数)。请你找一棵原图的生成树。设你找出的生成树中的边边权分别为 v_1,\cdots,v_{n-1}v1,,vn1,请你最大化 v_1\oplus v_2\oplus\cdots\oplus v_{n-1}v1v2vn1

输入输出格式

输入格式:

第一行两个正整数 n,mn,m

第二行一个长度为 ww 的串,串中的每个字符为 &、|、^ 中的一个(分别代表与、或和异或),表示每一个 \otimes_{o_i}oi

接下来 mm 行,每一行三个非负整数 x,y,vx,y,v,表示一条连接 xxyy 权值为 vv 的边,保证 1\leq x,y\leq n1x,yn0\le v < 2^w0v<2w

对于所有数据,1\le n\le 70,1\le m\le 5000,1\le w \le 121n70,1m5000,1w12

输出格式:

输出一行一个数,表示答案。如果图不连通,输出 -1。

输入输出样例

输入样例#1: 复制
3 3
^
1 2 1
2 3 1
1 3 0
输出样例#1: 复制
1

说明

关于数据

由于一些原因,数据只保留了最后 2020 个点。

#笔试题目#
全部评论

相关推荐

点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务