EvilStream~One Year~

vijos1395
一个简单的tree-dp:
背景 Background
HYH从来不相信世界上有NPC问题的存在，于是最近开始研究神奇的逻辑电路问题……

描述 Description
HYH逻辑电路是HYH最新发明的新型逻辑电路。
这个电路由三大元件组成，“And”（和）元件，“Or”（或）元件，“Xor”（异或）元件。每个元件都有两个元件通过电路向它输入信号，元件进行相应的处理后输出到下一个元件上，如图：

（红点为元件，蓝线为电路）
其中，信号只有两种：0和1，每个元件对信号进行的操作与普通逻辑运行规则相同：
And：和，信号同为1则输出1，其他情况输出0.
Or：或，两个信号中至少有一个1输出1，其他情况输出0。
Xor：异或，两个信号相同输出0，否则输出1。
HYH逻辑电路是一个设计好的逻辑电路，由用户输入一些信号，经过囧囧，啊不是，种种处理，就能在唯一的输出端上得到一个信号。可是，大部分用户发现， HYH逻辑电路无法对他们的信号得到他们想要的结果（？），于是准备投诉HYH。HYH很怕，所以他决定篡改最少数量的初始信号（越多越容易被发现嘛），使输出端信号改变。HYH的标程不用说又是萝莉控语言的，请您帮他设计出一个能在普通电脑上运行的程序。

输入格式 Input Format
首先第一行是两个数N和M，表示有N个元件，其中M个元件没有输入信号。元件被编号为1~N。
接下来的N行，第i行表示i号元件的情况，以x y z a表示输入信号的是x和y号元件，输出信号到z号元件，元件的种类是a。假设没有输入或者没有输出的元件则以0表示。
种类以1-3表示，1表示And，2表示Or，3表示Xor。
再接下来是M行，每行以x、y表示一个无输入信号的元件x的初始信号为y。不用检验数据正确与否，信号保证只有0、1两种可能。

输出格式 Output Format
输出只有一行，表示改变输出端信号最少要改变多少个初始元件。

题目出得很理解
首先想到xor,or,and不都是tmd双目运算符吗,又加上给了运算类型更加让人不知所云
最后看了题解里的牛人才知道原来那些运算类型什么的东西可以不鸟的
^$*(#^$&*#(^@$*&^#$&*^@#&*$^&*(@#^$&*(#^@$&*(^@#&*$^@#&*($^&*(@#
&*(%$#(%&*($#&%%$#%$#%我是没有意义的三角形#$%%#$%$%$#%#$%$#%$#%#$%
^$&*#(@^$&*^#&*($^(&*#@^$*#^&*$^*(#$^*&#^$(*^#@$&*^#@&*($^#
$#@$#@$#@$%^&#%$&%#$%#@^$%&#%$^&@#%$^%#@$^^$%#
$T#^@$*#^$&*^#*&$%^&#$&%#*$%#$&#%$*#%&%#@&$%^&
$#^$&*#(^$*^&#*@$(^*#$^(*^#$(*^#*$^(#@$^*^#$
$^#&$%&^#@%$&%&*%$%*%$&*#%$&%#$^^#@$^
$T#$^(#@$^&*(#^$*(#$^&*#@^$*&(#@^($*
$#&*$^*(&^#$(^@(#*$^*&#$^(*#$
$%#^$*%&#$%^&%*#&$%&#@
$^#$*(#^$*#^$*^*#$^
$^&#^$*#$(#$#
$^#&@$*
$#@$
#@$
@#
#
$
$
$
$
$
$

dp方程很容易想:
f[i,v]表示第i个点为1的最小代价
i.l,i.r:左右儿子
case #1(and)
f[i,1]=f[i.l,1]+f[i.r,1]
f[i,0]=min(
f[i.l,0]+f[i.r,1],
f[i.l,1]+f[i.r,0],
f[i.l,0]+f[i.r,0])
以下仅给出成立条件吧,我承认我偷懒了..
case #2(or)
f[i,0]可以由左右子树全为0转移
f[i,1]自然由其他3种情况转移了
case #3(xor)
f[i,0]由左右子树全为(0或1)转移(逻辑嵌套,我承认我又偷懒了….)
f[i,1]由其他两种情况转移

很高兴地写完程序,很高兴地交上去,结果得了80分….
最后发现是xor的转移写反了..查了非常久才查出来

^$&#*%^$%@#&*$^*&@#^$&*(@#%$^@#%$&*^#%@&$%
*@#%$$#$#$#@#%*@%#*#@%$^&#@%$^*%^$#%@
#%$#%@$&#@$#$@#$*$^*&(@#^$#@%$*
^&*我也是没有意义的三角形~$&$*%#@
&%$&*%%^$#@$#@@#$#@$%^%
^&@$$$@#$@#$#@@#*$&
^$&$#$#@$#@$@#$#*
@243#@$@#$3
$%@^#$%&
$@#$#@#
^$&#$
^&

这么得个80分,感觉很诡异
(省略一个没有意义的三角形,否则有人要ddos我了….)
以上.