首页 > 礼物
开通博客写题解
头像 Misaka_19614
发表于 2022-05-27 22:51:06
礼物 换根dp 题目大意 有一棵n( n≤1e6n \leq 1e6n≤1e6 )个节点的树 , 要求找到一个根使得下面等式最大 . ∑i=1n∑j=1nLCS(i,j)\sum_{i=1}^{n}\sum_{j=1}^{n}LCS(i,j)i=1∑n​j=1∑n​LCS(i,j) 解题思路 换根D 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 pop_py
发表于 2022-05-27 22:01:48
第一遍扫描只计算以该点为根的其子树部分的最优解 第二遍扫描利用父节点的最优解计算以该点为根的子树部分加其余部分最优解 void dfs1(int u,int fa){ int mx1 = 0,mx2 = 0; for(int i=head[u];~i;i=e[i].nxt){ 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”