#H1077. C. ‘Elaina’ Panda2134 和他的终极超越限界跨叙事层魔法技能树

C. ‘Elaina’ Panda2134 和他的终极超越限界跨叙事层魔法技能树

题目背景

Panda2134——或者现在也可以叫她“伟大的伊蕾娜大人”——已经成为了里泰尔德都首屈一指的女企业家。仰赖着她超强的魔法能力,她刚出道便斩获自然主义灵感竞赛(Naturalism Olympics of Inspiration,NOI2077,即主张运用可确定性分析的手段进行魔法创作、实验和结构的竞赛)第一名,瞬间引发全城关注。尽管里泰尔德都计算机相关龙头企业 CCF 的秘书长已经连任了 17 年,但据可靠传闻,2078 年他就打算将秘书长之位传给伊蕾娜。

但……现在的里泰尔德可能没有人知道,如今的伊蕾娜,已经是一个不再能使用魔法的“废人”。

题目描述

潘达来到 2077 年的一瞬间,脑内突然多出了一个极其复杂的神秘图案。终于适应好他的新身体并通过中间人 knb 接收到了 KS 的情报和援助后,他终于得到了一处闲暇;在汽车旅馆的房间里,他决定聚精会神地内视这个图案。

他惊讶地发现,自己只需要稍稍努力,这个图案就变得无比清晰:它是一个 nn 个结点,n1n-1 条边的无向连通图,或者也可以将其称之为树。树上的每个结点都蕴含着某种超越性的力量,仿佛只要理解它们就能把握这个世界的真相——他觉得这可能就是所谓的“魔法”(后来他知道,它们甚至是魔法的基本单元)。而这些边则是某种轻盈而优雅的链接,它们被另一种力量遮蔽,让潘达无法直接领会每条链接的重量。

他的直觉给予了他 mm 条领会魔法结点的路线。第 ii 条路线可以用一个三元组 (ui,vi,ci)(u_i, v_i, c_i) 表示,即潘达需要花费 cic_i 的时间理解这条魔法的奥妙,随后他便可以知道从 uiu_iviv_i 的链接的重量异或和。而这 nn 个结点中有 kk 个是构建魔法体系的核心,因此,潘达认为有必要知道它们两两之间魔法链接的重量异或和。他希望花费尽量少的时间来达成他的目的,而你,作为潘达颅内的逻辑计算神经元之一,不幸地分到了这个锅。

数据格式与约定

输入

第一行输入三个数 $n(2 \le n \le 100),m(0 \le m \le 400),k(2 \le k \le 12)$,分别代表魔法结点的数量、领会魔法结点的路线的数量、核心结点的数量。

接下来 n1n-1 行,每行两个正整数 x,yx,y,表示编号为 xx 的魔法结点和编号为 yy 的魔法结点之间有一条链接。

接下来 mm 行,每行三个正整数 ui,vi,ci(1ci109)u_i, v_i, c_i(1 \le c_i \le 10^9),表示第 ii 条路线对应的三元组。

最后一行输入 kk 个整数 a1,a2,,aka_1,a_2,\dots,a_k,表示每个核心结点的编号,保证 aia_i 两两不同且升序输入。

输出

如果潘达无法成功,在唯一的一行中输出 1-1

否则,在一行内输出一个整数 ci\sum{c_i} ,表示总共花费的时间。

样例

4 3 2
1 2
2 3
3 4
1 2 9
2 3 4
2 4 7
1 3
13

后记

“潘达爷,这次又得交给你了。”

“抱歉,我……可能不会再使用魔法了。”

“什么?!发生什么了?”

“……如果我没猜错的话,我每使用一次这些所谓的‘魔法’,这个世界的侵蚀都会加重。我所依赖的这种力量——它可能正在毁灭我们努力的一切。”