hnust_yangyanjun

题解

大数加法(1) 尺取法(1) 面经(4)

/ 注册

全部文章 / 题解（共3篇）

树学

题意：给你一颗树，你选择一个节点当根，求所有点的深度和最少为多少？思路：树状dp+换根一开始随便选一个点当根计算结果。dp[i]表示以i为根的子树节点的深度和。se[i]表示以i为根的子树的节点数目。换根：dp[v]=dp[u]+n-2*se[v];(v为u的子节点，根从u转向v时，以v为根的子树...

树状结构换根

2020-08-22

1 577

Accumulation Degree

题意：给予你一棵n个节点的树，每一条边有一个容量，你选择一个节点当根，求从根节点到叶子节点的流量的最大值。思路：树状dp+换根：flow[i]为以i为子树i到子树叶子节点的流量最大值。ans[i]表示以i为根节点时的答案。flow[u]= min(flow[v],cost(u,v))(v为u的子节...

换根树状dp

2020-08-22

1 775

Tree

题意：给与一棵n个节点的树，求每个点的连通点集的数量？思路：树形结构+换根dp[i]表示以i为根且包括i的这棵子树连通点集的数量。ans[i]表示包括i的连通点集的数量，既结果。父节点u与子节点v：dp[u]= (dp[v]+1) * dp[u];（v为u的子节点）换根时:ans[v]=((ans...

树形结构换根

2020-08-22

5 763