树
需要说吗？
直径
直径为树上一条边权和最长的简单路径，以下是直径的一些常用性质：
- 树的直径不一定唯一
- 树的直径的端点一定是度数为1的点
- 若直径有数条，那么所有直径交汇于至少一点
- 树上任一点距离其最远的点一定是直径的两个端点之一
- 在叶子节点处增加或删除一条边，直径至多增减1（边权为负数除外）
- 给定2棵树，添加一条边连接两棵树，新的树的直径至少为
max((d1+1)/2+(d2+1)/2+w,d1,d2)
具体实现方法为两遍DFS或BFS，第一次从任一点出发，找到离该点最远的点x，然后再调一次函数找到离x最远的点y，Sx->y就是直径的长度。
知道了这些相信你一定可以做出模板题了！
B4016 树的直径
模板参考代码注释即可。
#include<bits/stdc++.h>usingnamespacestd;vector<int>E[100005];intans=0,X,Y;voiddfs(intx,intfa,intid,intsum){if(sum>=ans){//如果目前的距离比原来更好就更新//等于为什么要更新呢？这是因为第二次深搜时ans没有清零，或者清零也行//可能第二次深搜答案刚好等于第一次深搜的答案，于是y就没有更新，最好加个等于号ans=sum;if(id==1){//第一次深搜X=x;}else{Y=x;}}for(inti=0;i<E[x].size();i++){intv=E[x][i];if(v==fa)continue;dfs(v,x,id,sum+1);//距离加一}}intmain(){intn;cin>>n;for(inti=1;i<n;i++){intu,v;cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}dfs(1,0,1,0);//第一次从任一点出发dfs(X,0,2,0);//第二次从x点出发cout<<ans;return0;}CF1404B Tree Tag
看题可得知题意：alice和bob依次在一棵树上轮流移动移动da和db的距离，问alice能否追到bob。
首先初始时如果它们之间的距离比da小，那么alice必胜，因为她先手，距离过小时可以直接抓到。就比如你要抓博尔特，贴脸抓，他还没开始跑你一伸手就抓到他了。
否则接着alice考虑最优策略：跑到直径的中间位置，这样她距离所有点最近，这样如果直径的一半向上取整小于等于da，那么alice必胜，因为这样无论bob跑到哪alice抓一下就抓到了。就比如你要抓博尔特，在厕所里面抓，博尔特无论跑到哪你都一定抓得到。
再否则不行，那么alice考虑最后的最优策略：把bob逼到叶子节点去，假设bob已经到叶子节点了，他还要脱离的话就得一次跳过alice的捕捉范围，也就是说要bob胜必须db>da*2，否则alice胜。就比如你要抓博尔特，在死胡同里抓，博尔特跑到最里面除非从你头上跳过去否则你都一定抓得到。
#include<bits/stdc++.h>usingnamespacestd;vector<int>E[100005];intans=0,X,dis[100005];voiddfs(intx,intfa,intsum){//找直径长度dis[x]=sum;if(sum>=ans){ans=sum;X=x;}for(inti=0;i<E[x].size();i++){intv=E[x][i];if(v==fa)continue;dfs(v,x,sum+1);}}intmain(){intt;cin>>t;while(t--){memset(dis,0,sizeofdis);ans=X=0;intn,a,b,da,db;cin>>n>>a>>b>>da>>db;for(inti=1;i<=n;i++)E[i].clear();for(inti=1;i<n;i++){intu,v;cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}dfs(a,0,0);intggy=dis[b];dfs(X,0,0);if(ggy<=da||db<=da*2||(ans+1)/2<=da){cout<<"Alice"<<endl;}else{cout<<"Bob"<<endl;}}return0;}
