一颗1为树根的无向树，小a在1，小b在m，小a总想最快靠近小b，小b总想最晚被接近，他们两个各走一步。问你最大的回合数（没回合一次） 以为是树的直径，从1和m分别求距离各点1和m的距离，然后取最大的（d1为各点到1的距离，d2为各点到m的距离，在这俩数组中找最大的一个。）。后来发现小b可以走分叉，那样会大于最大的点。。 。。 题中肯定会有一个点，小b在这里等小a。（不然小b不会被抓住qwq）。 我们可以枚举这个点 先计算 各点到m的距离。d1 在计算 各点到1的距离d2，同时后序遍历这个点之后的最大距离。x 如果d2>d1,意味着小b可以早到，在这里等小a一会，思考一下下一步咋走。。 然后d2+x，x就是小a之后要走的距离。。 枚举点求最大。 问：为什么不直接找一个最长的边呢。 答：因为会撞到a就不好了。 问：为什么计算的顺序不能反呢？ 答：我也是这样想的，后来反了一下，发现如果这样，那么x可能会与d1有重叠，那样会造成提前会抓住的情况。 http://codeforces.com/contest/813/problem/C
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #define maxn 200006 using namespace std; /*看完好久，才看懂了。 小a一定有一个点一直在等他，枚举那个点。 并且一定要先行计算1到m的距离。 因为1之后的延续和他相等可以， 但是m之后的延续不能和1到i的距离相等。 否则就提前相遇了 */ struct Node { int u; int v; int next; }node[maxn*2]; int head[maxn]; int len; int d1[maxn]; int d2[maxn]; int m; bool vis[maxn]; bool vis2[maxn]; int anss; void add(int a,int b) { node[len].u=a; node[len].v=b; node[len].next=head[a]; head[a]=len++; } int dfs1(int num) { for(int i=head[num];i!=-1;i=node[i].next) { int s=node[i].v; if(!vis[s]) { vis[s]=true; d1[s]=d1[num]+1; dfs1(s); } } return 0; } int dfs2(int num)//后序遍历 { //cout<<num<<"!!"<<endl; int sum=0; for(int i=head[num];i!=-1;i=node[i].next) { int s=node[i].v; if(!vis2[s]) { vis2[s]=true; d2[s]=d2[num]+1; int now=dfs2(s); sum=max(sum,now); } //cout<<sum<<" "<<num<<endl; } //cout<<sum<<" "<<num<<endl; if(d2[num]>d1[num]) { cout<<sum<<d1[num]<<num<<endl; anss=max(anss,2*(sum+d2[num])); //cout<<anss<<endl; } return sum+1; } void init() { memset(node,0,sizeof(node)); memset(head,-1,sizeof(head)); len=0; } int main() { int n; int a,b; scanf("%d%d",&n,&m); init(); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } memset(vis,false,sizeof(vis)); d1[m]=0; vis[m]=true; dfs1(m); memset(vis2,false,sizeof(vis2)); d2[1]=0; vis2[1]=true; anss=-1; dfs2(1); cout<<anss<<endl; return 0; }