←_←

题目链接 题意 给你一颗树多次询问，每次询问若干个节点，求最少删除几个节点使得任意两选中节点不连通，询问总共的点集不超过 100000100000100000 思路 先建个虚树，然后树形DP。 dp[u][0]dp[u][0]dp[u][0] 子树上没有选中点与 uuu 连通的最小花费 dp[u][1]dp[u][1]dp[u][1] 子树上不超过一个选中点与 uuu 连通的最小花费 转移方程见代...

题目链接 题意 给你一颗树边权为1多次询问，每次询问若干个点，求任意两点之间距离之和，最远点对权值，最近点对权值 思路 询问很多，但是询问总共的点集不超过 200000020000002000000 可以对每次查询建虚树，得到一颗新树后树形dp。 dp[u][0] 表示 子树中的询问节点数量 dp[u][1] 表示 以u为根节点子树中询问节点到u的最近距离 dp[u][1] 表示 以u为根节点子树...

题目链接 题意 给你个以 111 为根节点的树，树有边权 www （割断此边），多组询问每次询问给你 mmm 个点，求割断边最小花费使得 111 到这些点都不连通。 思路 询问如果组数少可以直接 O(n)O(n)O(n) 树形dp解决，这题询问很多，但是询问的点集不超过 500000500000500000 对于答案来说很多点是没有贡献的，每次查询有贡献的点只有所求点与所求点之间的 LCALCAL...