水一篇题解。也是一道并查集的好题，涉及另一个并查集的基本应用，并查集维护连通块（我跟并查集过不去了？？？）大致题意：给你一棵树，对于每次询问求一个点所在连通块中到达该点的最小路径权值大于给定值的点个数。既然都连通块了，那我们在维护连通块的时候直接不把权值大于K的边加进去，用并查

题目首先有结论：一个点为关键点（可以由该点的子树中出发，正好在该点拦截住奶牛），当且仅当\(g_u\ledist(root,u),g_{fa}>dist(root,fa)\),其中\(g_u\)表示距离\(u\)最近的叶节点。那么\(18pts\)就是\(O(n^2)\)的暴力了voiddfs(intu,intfa){ dis[u]=(G.d[u]==

Description贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有\(N\)个结点的树，结点分别编号为\(1,2,\ldots,N\)。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了

P4182[USACO18JAN]LifeguardsP更好的阅读体验提供一个比较优秀大常数的时间\(\mathcalO(nm)\)，空间线性的做法。由于变量名冲突，本文中\(m\)均指题目中的\(k\)。推推性质，发现若区间包含了另一个区间，则一定删掉被包含的区间，正确性显然。这样我们得到了一些左右端点都递增

题意分析我们首先想到，枚举贝茜在\(x\)点，枚举度数大于\(2\)的点为\(y\)。设\(x\)的度数为\(a\)，\(y\)的度数为\(b\)。我们首先发现每个\(x\)点都有一个初始的贡献为\(a\)条通往叶子的路径。如果点\(y\)到最近的叶子节点的距离大于到\(x\)的点的距离（农夫不能在

题目链接可以发现，对于一个固定的\(k\)，所有边权小于\(k\)的边对答案是没有贡献的，因为一条边的相关性是最小相关性，这也意味着我们不能从\(<k\)的边到达其他的点。由于本题有多组询问，所以对于没有用的边，将其看做被删除，有用的边，将其看做被插入。考虑到本题实际上要维护连通块