找树
题目描述
定义 \otimes_1, \otimes_2, \otimes_3⊗1,⊗2,⊗3 分别为按位与、按位或、按位异或运算。记 a_iai 表示 aa 的从低位到高位的第 ii 个二进制位。定义一个作用在 ww 位二进制数上的新运算 \oplus⊕,满足对于结果 a\oplus ba⊕b 的每一位 (a\oplus b)_i(a⊕b)i 有 (a\oplus b)_i = a_i \otimes_{o_i} b_i(a⊕b)i=ai⊗oibi。不难验证 \oplus⊕ 运算满足结合律和交换律。
给出一张 nn 个点 mm 条边的无向图,每一条边的权值是一个 ww 位二进制数(即小于 2^w2w 的非负整数)。请你找一棵原图的生成树。设你找出的生成树中的边边权分别为 v_1,\cdots,v_{n-1}v1,⋯,vn−1,请你最大化 v_1\oplus v_2\oplus\cdots\oplus v_{n-1}v1⊕v2⊕⋯⊕vn−1。
输入输出格式
输入格式:第一行两个正整数 n,mn,m;
第二行一个长度为 ww 的串,串中的每个字符为 &、|、^ 中的一个(分别代表与、或和异或),表示每一个 \otimes_{o_i}⊗oi。
接下来 mm 行,每一行三个非负整数 x,y,vx,y,v,表示一条连接 xx 和 yy 权值为 vv 的边,保证 1\leq x,y\leq n1≤x,y≤n,0\le v < 2^w0≤v<2w。
对于所有数据,1\le n\le 70,1\le m\le 5000,1\le w \le 121≤n≤70,1≤m≤5000,1≤w≤12。
输出格式:输出一行一个数,表示答案。如果图不连通,输出 -1。
输入输出样例
说明
关于数据
由于一些原因,数据只保留了最后 2020 个点。
#笔试题目#