核心内容摘要
还在手动配置MCP？Cursor+MCP生态库：一键解锁AI的千种超能力！
树需要说吗直径直径为树上一条边权和最长的简单路径以下是直径的一些常用性质树的直径不一定唯一树的直径的端点一定是度数为1的点若直径有数条那么所有直径交汇于至少一点树上任一点距离其最远的点一定是直径的两个端点之一在叶子节点处增加或删除一条边直径至多增减1边权为负数除外给定2棵树添加一条边连接两棵树新的树的直径至少为max((d
/2(d
/2w,d1,d
具体实现方法为两遍DFS或BFS第一次从任一点出发找到离该点最远的点x然后再调一次函数找到离x最远的点ySx-y就是直径的长度。
知道了这些相信你一定可以做出模板题了B4016 树的直径模板参考代码注释即可。
#includebits/stdc.husingnamespacestd;vectorintE[100005];intans0,X,Y;voiddfs(intx,intfa,intid,intsum){if(sumans){//如果目前的距离比原来更好就更新//等于为什么要更新呢这是因为第二次深搜时ans没有清零或者清零也行//可能第二次深搜答案刚好等于第一次深搜的答案于是y就没有更新最好加个等于号anssum;if(id
{//第一次深搜Xx;}else{Yx;}}for(inti0;iE[x].size();i){intvE[x][i];if(vfa)continue;dfs(v,x,id,sum
;//距离加一}}intmain(){intn;cinn;for(inti1;in;i){intu,v;cinuv;E[u].push_back(v);E[v].push_back(u);}dfs(1,0,1,
;//第一次从任一点出发dfs(X,0,2,
;//第二次从x点出发coutans;return0;}CF1404B Tree Tag看题可得知题意alice和bob依次在一棵树上轮流移动移动da和db的距离问alice能否追到bob。
首先初始时如果它们之间的距离比da小那么alice必胜因为她先手距离过小时可以直接抓到。
就比如你要抓博尔特贴脸抓他还没开始跑你一伸手就抓到他了。
否则接着alice考虑最优策略跑到直径的中间位置这样她距离所有点最近这样如果直径的一半向上取整小于等于da那么alice必胜因为这样无论bob跑到哪alice抓一下就抓到了。
就比如你要抓博尔特在厕所里面抓博尔特无论跑到哪你都一定抓得到。
再否则不行那么alice考虑最后的最优策略把bob逼到叶子节点去假设bob已经到叶子节点了他还要脱离的话就得一次跳过alice的捕捉范围也就是说要bob胜必须dbda*2否则alice胜。
就比如你要抓博尔特在死胡同里抓博尔特跑到最里面除非从你头上跳过去否则你都一定抓得到。
#includebits/stdc.husingnamespacestd;vectorintE[100005];intans0,X,dis[100005];voiddfs(intx,intfa,intsum){//找直径长度dis[x]sum;if(sumans){anssum;Xx;}for(inti0;iE[x].size();i){intvE[x][i];if(vfa)continue;dfs(v,x,sum