点的距离_系统运维

概述#include <iostream>#include <cstdio>#include <string>using namespace std;int dfn[500001], f[500001][21];int n, m, cnt, root;int head[500001], lg[500001];struct tu { int v, nxt;} e

#include <iostream>#include <cstdio>#include <string>using namespace std;int dfn[500001],f[500001][21];int n,m,cnt,root;int head[500001],lg[500001];struct tu {    int v,nxt;} e[5000001];voID add(int u,int v) {    e[++cnt].v = v;    e[cnt].nxt = head[u];    head[u] = cnt;}voID dfs(int Now,int fa) {    dfn[Now] = dfn[fa] + 1;    f[Now][0] = fa;    for (int i = 1; (1 << i) <= dfn[Now]; i++) f[Now][i] = f[f[Now][i - 1]][i - 1];    for (int i = head[Now]; i; i = e[i].nxt) {        if (e[i].v != fa)            dfs(e[i].v,Now);    }}int lca(int x,int y) {    if (dfn[x] < dfn[y])        swap(x,y);    while (dfn[x] > dfn[y]) {        x = f[x][lg[dfn[x] - dfn[y]]];    }    if (x == y)        return x;    for (int k = lg[dfn[x]]; k >= 0; k--)        if (f[x][k] != f[y][k])            x = f[x][k],y = f[y][k];    return f[x][0];}int main() {    scanf("%d",&n);    for (int i = 1; i <= n - 1; i++) {        int x,y;        scanf("%d%d",&x,&y);        add(x,y);        add(y,x);    }    dfs(1,0);    lg[0] = -1;    for (int i = 1; i <= n; i++) lg[i] = lg[i >> 1] + 1;  //求log+1    // for(int i=1;i<=n;i++)    // printf("%d ",lg[i]);    scanf("%d",&m);    for (int i = 1; i <= m; i++) {        int x,&y);        int mm = dfn[lca(x,y)];        printf("%d\n",dfn[x] - mm + dfn[y] - mm);    }    return 0;}