hdoj4705–2013多校第10场Y题

树形dp:
dp[i]表示结点i为根的子树中无法形成简单路径的点对数。有如下几种情况:
(1)对于以点i为根的子树,两个点在i的一颗子树中(不成祖先后代关系),还有一个点在i的另一棵子树中。
(2)3个点分散在i的三棵子树中(i存在三个儿子的情况下)
比赛的时候很快就想到了这个,思路很简单,但是在想细节的时候,发现对于第二种情况是3次方枚举,然后队友说这题差不多了,我就没再想,去看其他题了,交给队友敲。后来发现队友TLE了,才知道他也是三次方的枚举。。。这,早点交流其实可以避免。。三次方必然超时嘛。。
然后俩队友讨论出了线性时间的方法,后来我又回来看这题(==这场的网络流好难。。),听队友讲了线性时间解决方法,似懂非懂。于是决定自己推。。推出来和队友的还是有些不一样的。。多算了些东东,多减了些东东
本质:对于n个数,a1~an,O(n)时间求其中下标不重复的三个数的积的总和(组合而非排列:a1*a2*a3和a2*a3*a1是一样的)。
设s=a1+a2+……+an,c=a1^2+a2^2+……+an^2所求答案为ans
在稿纸上算一下:ans=(s^3-[a1*(c-a1^2)+a2*(c-a2^2)+……+an*(c-an^2)]+[a1^2*(s-a1)+a2^2*(s-a2)+……+an^2*(s-an)]+s*c)/6;
仔细打下草稿还是可以出来的,最后除以3!是因为三个数进行了全排列。

树形dp专题(更新ing)

前段时间做线段树,结果做不下去了。。感觉dp太弱,遂打算做个专题,tree dp之后是状压,往后是数位dp和概率dp,不过图论也要抓起来
几个链接:
背包九讲:http://wenku.baidu.com/view/519124da5022aaea998f0f22.html
论文《几类背包问题》:http://wenku.baidu.com/view/8ab3daef5ef7ba0d4a733b25.html
依赖背包博文:http://www.cnblogs.com/GXZC/archive/2013/01/13/2858649.html
zero clock背包总结:http://blog.csdn.net/woshi250hua/article/details/7636866
开个树形dp专题:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25888#overview
(一)一般树形dp
(二)树形dp+分组背包
因为有分支,所以树上的背包要容量要分配,但是因为是依赖背包,所以根一定要选。从根往下看是分配,代码中实际是从叶子往上合并的,这种合并其实就是dd神牛的背包九讲里面的泛化物品,实质是把对一棵子树的决策(分配多少容量给该子树,因为决策互斥)作为一件物品,这样,合并=实际上就是做一次分组背包,一棵子树就是一个组,每组物品有dp[son][0]~dp[son][V-w[fa]]。为什么是V-w[fa]呢,因为父节点时一定要选的,所以给子节点的容量最多也就V-w[fa]。
////////////////////////////////////
hdoj1561
典型的依赖背包,因为可能是深林,所以以0为虚拟根,val[0]=0,w[0]=1;

hdoj2196——两次树形dp(下->上、上->下)

开始想的太简单,以为到树中某点的距离最远的点只有两种情况:1.在以该点为根的子树的某个叶节点。2.从该点往上经过根结点,在从根结点到最远结点。
而事实上,看了网上的解题报告才发现,从某点往上的最远距离不一定经过根结点,但一定经过父节点。
dp[i].first表示以i点为根的子树中到点i的最远距离
dp[i].second表示以i点为根的子树中到点i的次远距离
dp[i].sonid表示对应于dp[i].first的i的那个儿子编号
(注意:上面的second指的是不和dp[i].first经过i的同一个儿子节点的最远距离)
dp2[i]表示经过i点的父亲的最远距离
这样两次dfs即可。第一次从下往上更新dp,第二次从上往下更新dp2(由于是从上往下更新,所以求解dp2[i->son]时用到的dp2[i]已经正确求解出来了,这样就保证了正确性)。

hdoj1520

哈哈,第一道树形dp,这题其实就是树的最大权独立集,用了两种方式存储树
dp[i][0]:当结点i不选时,以i为根的子树能取得的最大权值
dp[i][1]:当结点i选中时,以i为根的子树能取得的最大权值
vector版本