链式前向星O(m)

// 链式前向星
// h[] 存的是单链表头，e[i]存的是第i条边指向哪个点，ne[i]指的是与这条边起点相同的上一个节点的编号
int h[N], e[M], ne[M], idx; // idx是边的编号，链式前向星的写法存储效率是O(m)

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++; // 第1条边插入的时候ne->h[a](==-1)
}

树的重心

求树中节点个数的代码：

int dfs(int u)
{
    int sum = 1;  // 初始化为1，算上当前节点u自身
    st[u] = true;
    for (int i = h[u]; i!= -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            sum += dfs(j);  // 递归计算子树节点个数并累加
        }
    }
    return sum;
}