HDU 5735 Born Slippy(拆值DP+位运算)

 

【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5735

 

【题目大意】

   给出一棵树,树上每个节点都有一个权值w,w不超过216,树的根为1,从一个点往根的方向走,可以得到他的祖先序列,现在需要从v1点的祖先序列中挑选出一定数量的点,组成数列v1,v2,v3……vm,要求vi是vi-1的祖先,求dp[v1]=max(dp[vi]+(w[v1] opt w[vi])),opt是一种运算,在题目中可为xor,or或者and,最后求出ans=sum_{i=1}^{n}(i*(w[i]+dp[i]))

Posted by forever97 2016年7月24日 20:55