题目来源：URAL 1752. Tree 2

题意：求一个点v与它距离为d的任意一个点 没有输出0

思路：开始想倍增法 但是倍增法只能往他的祖先去 后来百度发现了树的直径 想了想 发现可以建2棵树 每一棵树的根是树的直径的2个端点

这样保证了每个点和他距离最远的点就是其中一个根 因为一个点到树的直径的端点的距离是最远的 最后就是LCA倍增了

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 50010; const int INF = 0x3f3f3f3f; int anc[maxn][30][2]; int fa[maxn][2], L[maxn], vis[maxn], d[2][maxn], to[maxn]; int n, m; int first[maxn], cnt; struct edge { int u, v, next; }e[maxn*2]; void AddEdge(int u, int v) { e[cnt].v = v; e[cnt].next = first[u]; first[u] = cnt++; e[cnt].v = u; e[cnt].next = first[v]; first[v] = cnt++; } void pre() { for(int k = 0; k < 2; k++) { for(int i = 1; i <= n; i++) { anc[i][0][k] = fa[i][k]; for(int j = 1; (1<
      
       = 0; i--) { if(d-(1<
       
        = 0) { d -= (1<
        
          Q; Q.push(u); int rt = u, dis = -1; while(!Q.empty()) { int x = Q.front(); Q.pop(); if(d[k][x] > dis) { dis = d[k][x]; rt = x; } for(int i = first[x]; i != -1; i = e[i].next) { int v = e[i].v; if(vis[v]) continue; vis[v] = 1; d[k][v] = d[k][x] + 1; fa[v][k] = x; Q.push(v); } } for(int i = 1; i <= n; i++) to[i] = max(to[i], d[k][i]); return rt; } int main() { while(scanf("%d %d", &n, &m) != EOF) { memset(first, -1, sizeof(first)); cnt = 0; for(int i = 1; i < n; i++) { int u, v; scanf("%d %d", &u, &v); AddEdge(u, v); } memset(to, 0, sizeof(to)); int s = BFS(1, 0); int t = BFS(s, 1); BFS(t, 0); pre(); while(m--) { int v, dis; scanf("%d %d", &v, &dis); //printf("***%d %d %d\n", to[v], d[0][v], d[1][v]); if(to[v] < dis) { puts("0"); continue; } if(d[0][v] > d[1][v]) printf("%d\n", query(0, v, dis)); else printf("%d\n", query(1, v, dis)); } } return 0; }