/*

节点维护的信息多样

如果用树状数组维护到根节点的边权或者点权, 可以直接插入点权和边权值,不需要预处理,

但是记得一定要使用ot[]消除影响.即差分.    Housewife Wind  这个坑踩得死死得.

然后如果带修改,也可以线段树维护.

打上dfs序后, 其他的就是区间问题了. 然后查询 修改的时候,把dfs序与点或者边对应转换一下就OK了.

*/

int deep[maxn];

int up[maxn][];

int   in[maxn];  // dfs序 入

int   ot[maxn];  // dfs序 出

int   pa[maxn];  // father 数组

int qsz, qtot;

// 预处理出 deep[] in[] ot[] pa[] up[i][0]

void dfs(int u, int fa)

{

    int i, v;

    deep[u] = deep[fa] + ;

    in[u] = qtot;

    for (i=head[u]; i; i=edge[i].lst) {

        v = edge[i].to;

        if (v == fa) continue;

        up[v][] = u;

        pa[v] = u;

        ++qtot;  // dfs序标号用.

        dfs(v, u);

    }

    ot[u] = qtot;

}

// 获取公共祖先的表.

void GetUp(int n)

{

    int i, j;

    for (j=; j<; ++j)

        for (i=; i<=n; ++i)

            up[i][j] = up[up[i][j-]][j-];

}

// 倍增求lca

int lca(int u, int v)

{

    if (deep[u] < deep[v]) swap(u, v);

    int i, j, k = deep[u] - deep[v];

    for (i=; i<; ++i) // 获取第k个祖先

        if ((<<i) & k)

            u = up[u][i];

    if (u != v) {

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

            if (up[u][i] != up[v][i]) {

                u = up[u][i];

                v = up[v][i];

            }

        u = up[u][];

    }

    return u;

}

int main()

{

    // 多Cas记得清零 up[][] 之类的数组  还有全局变量

    deep[] = ;

    dfs(, );

    GetUp(n);  // 在dfs()预处理出各节点的父亲后调用. 

    return ;

}