int Find (int x) {

    return x == pre[x] ? x:pre[x] = Find(pre[x]);

}

void dfs(int x,int w,int fa) {

    d[x] = w;    //点x的深度

    //遍历与点x相连的点（除了已经访问过的和其父节点）

    for (int i = ; i < v[x].size(); i++) {

        if (!vis[v[x][i]] && v[x][i] != fa) {

            dfs(v[x][i],w+,x);

            pre[v[x][i]] = x;

            vis[v[x][i]] = ;

        }

    }

    //访问所有和x有询问关系的e

    //如果e被访问过;

　　 //x,e的最近公共祖先为find(e);

}

void dfs(int f,int u){

    fa[u]=f;

    d[u]=d[f]+;

    for (int i=;i<v[u].size();i++)

        if (v[u][i]!=f) dfs(u,v[u][i]);

}

int LCA(int a,int b){

    if (d[a]>d[b])

        swap(a,b);

    while (d[b]>d[a]) b=fa[b];

    while (a!=b) a=fa[a],b=fa[b];

    return a;

}

void dfs(int f,int u) {

    fa[u][] = f;

    dep[u] = dep[f] + ;

    for (int i = ; i <= ; i++) {

        fa[u][i] = fa[fa[u][i-]][i-];

        //其他操作

    }

    for (int i = ; i < v[u].size(); i++) {

        if (f == v[u][i]) continue;

        dfs(u,v[u][i]);

    }

}

void lca(int x,int y) {

    memset(ans,,sizeof(ans));

    if (dep[x] < dep[y]) swap(x,y);

    for (int i = ; i >= ; i--)

        if (dep[fa[x][i]] >= dep[y]) {

            //其他操作

            x = fa[x][i];

        }

    if (x == y) {

        return;

    }

    for (int i = ; i >= ; i--)

        if (fa[x][i] != fa[y][i]) {

            //其他操作

            x = fa[x][i],y = fa[y][i];

        }

}