#P51974. 「THUPC 2019」找树 / findtree

「THUPC 2019」找树 / findtree

题目描述

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

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

输入格式

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

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

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

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

输出格式

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

样例

3 3
^
1 2 1
2 3 1
1 3 0
1

数据范围与提示

来自 THUPC(THU Programming Contest,清华大学程序设计竞赛)2019。

题解等资源可在 https://github.com/wangyurzee7/THUPC2019 查看。