题解
从一棵树里面找三个点$x,y,z$,从点$x$出发,先到另外两个点中离$x$较近的点,然后再到剩下那个点的路径和最大.首先对于直径两端点是必然选择,然后枚举起点,统计答案即可
bzoj1912(树形dp)
Posted on
| In
dp
题解
$ k=1 $ 必然连接直径两端
我们考虑$ k=2 $的情况 首先明确选的两条路径 选直径是否还是最优的?当然,不管如何考虑选直径带来的优势要大于不选直径 然后对于第二条路的选择 如果第二条路和直径有交边 那么交边还是会经过两次 那么就是让 两条路径并起来的部分减去交的部分长度最长 我们可
...
bzoj4987(树形dp)
Posted on
| In
dp
题解首先,$\sum_{i=1}^{k-1} dis(a_i,a_{i+1})$ 最小化 那么对于这$k$个点的选择可见必然是一个连通子树 可以反证 如何统计价值呢?我们考虑对于一棵树如何遍历每个点让路径和最小 显然是 $ 2sum-len$ 即2倍路径和减去直径 这样子我们可以设$dp[i]
...
bzoj3124(树形dp)
Posted on
| In
dp
题解:我们考虑找出任意一条直径的两个端点$x$,$y$ 对直径上的节点打上标记 对于其他不在直径上的点$v$ 找到其离的最近的标记点$pos$ 我们考虑当前$dis[pos]-dis[x]$与$dis[y]-dis[pos]$的大小关系然后判断$v$是否为分叉直径上的节点 若是则对原标记节点打上标
...