「BZOJ4016」[FJOI2014] 最短路径树问题

2014年12月15日4,8875

cxjyxx_me:

先求一个最短路图 然后再这个图上dfs 对于一个点的所有出点 按编号从小到大dfs
这样可以保证dfs树就是题目要求的树
然后在这棵树上跑树分治 f[i][j][2]表示前i棵子树 从根出发链长为j [0:最长长度][1:这个长度条件下的方案数]
对于第i+1棵子树 单独跑一个f’[i][j][2]意义一样 枚举这颗子树上链长 和f一起更新答案 然后用f‘更新f

 

说点什么

提醒
avatar
一个人看日落

黄学长~貌似第131行那个应该是S – size[x]意义才对的样子Orz,虽然不知道为什么改不改交BZOJ都是可以过的。

WuHongxun
WuHongxun

TAT求题面

ShinriiTin
ShinriiTin

黄学长,求这题题号