小绿的房子时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述B 市的地图是一棵有n nn个节点的树每个节点上都有房子出售。小棕和小绿是一对好朋友他们近期都准备在 B 市买房。为了方便周末一起玩小绿希望他的房子一定不要离小棕的太远。不过为了给小棕一个惊喜小绿没有去找小棕问他买在哪里他希望能直接在图上找到一些点这些点满足距离其他任意点的距离都不超过2 22。这样只要他这些点上买房那么无论小棕的房子在哪里他们之间的距离都不会超过2 22了。现在小绿来求助于你而你只需要告诉他有多个满足他要求的点就行。输入描述第一行输入一个正整数n nn表示树的大小。接下来的n − 1 n - 1n−1行每行输入两个正整数u , v u, vu,v代表节点u uu和节点v vv有一条边连接。1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤1051 ≤ u , v ≤ 10 5 1 \le u, v \le 10^51≤u,v≤105保证输入的是一棵树。输出描述输出一个正整数距离所有其他点距离都不超过2 22的点的个数。示例 1输入6 1 2 2 3 4 3 5 2 3 6输出2说明2 22和3 33两个点都是离其他点的距离不超过2 22的点。数据范围与提示1 ≤ n ≤ 10 5 1 \le n \le 10^51≤n≤105输入保证是一棵树核心思路「到其他所有点的距离都不超过2 22」等价于「以该点为根时树的高度不超过2 22」也就是该点的离心率≤ 2 \le 2≤2。树上一个点的最远距离等于它到直径两端点距离的较大值经典结论。因此先两次 BFS/DFS 求出直径端点s ss与t tt再对每个点v vv判断max ⁡ ( d i s t ( s , v ) , d i s t ( t , v ) ) ≤ 2 \max(\mathrm{dist}(s, v),\ \mathrm{dist}(t, v)) \le 2max(dist(s,v),dist(t,v))≤2成立即计入答案。也可以先求直径长度d dd若d 4 d 4d4则无解答案0 00否则答案就是直径中点及其相邻的、满足条件的点直接按上述判定统计即可。时间复杂度O ( n ) O(n)O(n)注意n nn达10 5 10^5105同样建议使用迭代式 BFS 避免递归爆栈。解题思路本题是树形动态规划求离心率的经典问题。给定一棵n nn个节点的树要求统计有多少个节点满足到其他任意节点的距离都不超过2 22。这等价于该节点的离心率到最远节点的距离不超过2 22。利用树形 DP 分别求出每个节点向下的最长路径和向上的最长路径取二者较大值即为离心率判断是否≤ 2 \le 2≤2即可。1. 问题等价转化对于树上的节点u uu其离心率定义为max ⁡ v d i s t ( u , v ) \max_{v} \mathrm{dist}(u, v)maxv​dist(u,v)。题目要求max ⁡ v d i s t ( u , v ) ≤ 2 \max_{v} \mathrm{dist}(u, v) \le 2maxv​dist(u,v)≤2即从u uu出发到任意节点的距离都不超过2 22。树的离心率可以通过两次树形 DP 求得向下最长路径在u uu的子树中从u uu出发能到达的最远距离记为dp[u][0]次远距离记为dp[u][1]用于处理向上路径时避免重复走同一子树。向上最长路径从u uu出发经过父节点方向能到达的最远距离记为up[u]。节点u uu的离心率即为max ⁡ ( dp [ u ] [ 0 ] , up [ u ] ) \max(\text{dp}[u][0], \text{up}[u])max(dp[u][0],up[u])。若该值≤ 2 \le 2≤2则u uu满足条件。2. 算法实现两次 DFS建图使用链式前向星存储无向树每条边双向添加。第一次 DFS后序遍历计算每个节点向下的最长和次长路径。从根节点1 11开始递归访问子节点。对于节点u uu初始化dp[u][0] dp[u][1] 0。遍历子节点v vv递归后得到dp[v][0] 1边权为1 11。若该值大于dp[u][0]则更新次长dp[u][1] dp[u][0]最长dp[u][0] dp[v][0] 1否则若大于dp[u][1]更新dp[u][1]。第二次 DFS前序遍历计算每个节点向上的最长路径并统计答案。从根节点1 11开始初始up[1] 0。对于节点u uu判断离心率max ⁡ ( dp [ u ] [ 0 ] , up [ u ] ) ≤ 2 \max(\text{dp}[u][0], \text{up}[u]) \le 2max(dp[u][0],up[u])≤2是否成立若成立则ans。对于每个子节点v vv计算v vv的向上最长路径若v vv是u uu向下最长路径的来源即dp[v][0] 1 dp[u][0]则v vv向上经过u uu能到达的最远距离为max ⁡ ( up [ u ] , dp [ u ] [ 1 ] ) 1 \max(\text{up}[u], \text{dp}[u][1]) 1max(up[u],dp[u][1])1。否则v vv向上经过u uu能到达的最远距离为max ⁡ ( up [ u ] , dp [ u ] [ 0 ] ) 1 \max(\text{up}[u], \text{dp}[u][0]) 1max(up[u],dp[u][0])1。将计算出的值作为v vv的up[v]递归处理v vv。输出ans即为满足条件的节点数量。3. 复杂度分析时间复杂度两次 DFS 均遍历所有节点和边一次每次操作O ( 1 ) O(1)O(1)总时间复杂度O ( n ) O(n)O(n)。n ≤ 10 5 n \le 10^5n≤105完全可行。空间复杂度链式前向星存储边O ( n ) O(n)O(n)DP 数组O ( n ) O(n)O(n)递归栈深度最坏O ( n ) O(n)O(n)。总空间O ( n ) O(n)O(n)。总结通过两次树形 DP 分别求出每个节点向下的最长/次长路径和向上的最长路径从而得到离心率。只需判断离心率是否≤ 2 \le 2≤2即可统计满足条件的节点数。方法直观高效是树形 DP 求离心率的典型应用。代码简要说明链式前向星h[N]头指针e[M]存储终点ne[M]存储下一条边idx为边计数器。add(a, b)添加无向边。数组dp[N][2]dp[u][0]存储u uu向下最长距离dp[u][1]存储次长距离。dfs_1(u, fa)后序遍历计算以u uu为根的子树中向下最长和次长路径。dfs_2(u, fa, root)前序遍历root表示从父节点方向到u uu的最长距离已包含父节点到u uu的边。首先判断离心率是否≤ 2 \le 2≤2然后为每个子节点计算新的root并递归。主函数读入n nn建图调用dfs_1(1, -1)和dfs_2(1, -1, 0)输出ans。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N100010;constll M200010;constll INF1e18;constll mod1e97;ll n;ll h[N],e[M],ne[M],idx;ll dp[N][2];ll ans;voidadd(ll a,ll b){e[idx]b;ne[idx]h[a];h[a]idx;}voiddfs_1(ll u,ll fa){for(ll ih[u];~i;ine[i]){ll je[i];if(jfa)continue;dfs_1(j,u);if(dp[j][0]1dp[u][0]){dp[u][1]dp[u][0];dp[u][0]dp[j][0]1;}elseif(dp[j][0]1dp[u][1])dp[u][1]dp[j][0]1;}}voiddfs_2(ll u,ll fa,ll root){if(root2dp[u][0]2)ans;for(ll ih[u];~i;ine[i]){ll je[i];if(jfa)continue;ll tmproot;if(dp[j][0]1dp[u][0])tmpmax(tmp,dp[u][1]);elsetmpmax(tmp,dp[u][0]);dfs_2(j,u,tmp1);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,n);memset(h,-1,sizeofh);for(ll i1;in;i){ll u,v;scanf(%lld%lld,u,v);add(u,v),add(v,u);}dfs_1(1,-1);dfs_2(1,-1,0);printf(%lld\n,ans);return0;}