2007年10月6日

[图论]pku3417

摘要: 我的做法是，对于每条新边，记录树中与之对应的路径。然后对于每条树边，统计被对应的次数。最后记录每个点到树根的路径上，有多少个1（设为q[i]）。对于新边(x,y)，它对答案的贡献就是q[x] + q[y] - 2q[lca(x,y)]。除了这些，答案还应加上树中0边的数量 * m。

阅读全文

posted @ 2007-10-06 20:53 Felicia 阅读(494) | 评论 (0) | 编辑收藏

导航

常用链接

留言簿(21)

随笔分类(145)

随笔档案(149)

相册

ACMers

Pretty Girls

最新随笔

搜索

最新评论

阅读排行榜

评论排行榜

2007年10月6日