树与图

倍增 LCA

// ============================================================
// 倍增 LCA（无权树，点编号 1..n）
// ============================================================
// 支持：LCA、k 级祖先、两点距离、祖先判断、路径上的第 k 个点。
// kth_on_path(x, y, k) 中 k 从 0 开始：k=0 返回 x。
// get_kth_ancestor(x, k) 若跳到根上方，返回 0。
//
// 如果是带权树：
//   把 adj 改为 vector<vector<pair<int,int>>>，DFS 时维护 dist[u]；
//   距离改成 dist[x] + dist[y] - 2 * dist[lca]。
//   up 表本身不需要改变。
// ============================================================
 
class LCA
{
private:
    int n, LOG, root, timer;
    vector<vector<int>> up;
    vector<int> depth, tin, tout;
 
    void dfs(int u, int parent, const vector<vector<int>> &adj)
    {
        tin[u] = ++timer;
        up[u][0] = parent;
        for (int j = 1; j < LOG; j++)
        {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
 
        for (int nxt : adj[u])
        {
            if (nxt == parent)
            {
                continue;
            }
            depth[nxt] = depth[u] + 1;
            dfs(nxt, u, adj);
        }
        tout[u] = timer;
    }
 
public:
    LCA(const vector<vector<int>> &adj, int root = 1)
        : n(adj.size() - 1), LOG(__lg(max(1ll, n)) + 2), root(root), timer(0),
          up(n + 1, vector<int>(LOG)), depth(n + 1), tin(n + 1), tout(n + 1)
    {
        dfs(root, 0, adj);
    }
 
    bool is_ancestor(int x, int y) const
    {
        return tin[x] <= tin[y] and tout[y] <= tout[x];
    }
 
    int get_kth_ancestor(int x, int k) const
    {
        for (int j = 0; j < LOG and x; j++)
        {
            if (k >> j & 1)
            {
                x = up[x][j];
            }
        }
        return x;
    }
 
    int getlca(int x, int y) const
    {
        if (is_ancestor(x, y))
        {
            return x;
        }
        if (is_ancestor(y, x))
        {
            return y;
        }
 
        for (int j = LOG - 1; j >= 0; j--)
        {
            if (up[x][j] and !is_ancestor(up[x][j], y))
            {
                x = up[x][j];
            }
        }
        return up[x][0];
    }
 
    int getfa(int x) const
    {
        return up[x][0];
    }
 
    int getdepth(int x) const
    {
        return depth[x];
    }
 
    int distance(int x, int y) const
    {
        int z = getlca(x, y);
        return depth[x] + depth[y] - 2 * depth[z];
    }
 
    int kth_on_path(int x, int y, int k) const
    {
        int z = getlca(x, y);
        int up_len = depth[x] - depth[z];
        int total = up_len + depth[y] - depth[z];
        if (k < 0 or k > total)
        {
            return 0;
        }
        if (k <= up_len)
        {
            return get_kth_ancestor(x, k);
        }
        return get_kth_ancestor(y, total - k);
    }
};

Tarjan 离线 LCA

// ============================================================
// Tarjan 离线 LCA
// ============================================================
// adj 使用 1 下标；queries[i] = {x, y}。
// 返回 ans[i]，顺序与输入询问完全一致。
// 复杂度约 O((n + q) alpha(n))，适合全部询问预先给出的情况。
// 如果还要在线回答新询问，应使用倍增 LCA，而不是 Tarjan 离线算法。
// ============================================================
 
vector<int> tarjan_lca(const vector<vector<int>> &adj,
                       const vector<pair<int, int>> &queries,
                       int root = 1)
{
    int n = adj.size() - 1;
    vector<vector<pair<int, int>>> q(n + 1);
    for (int i = 0; i < (int)queries.size(); i++)
    {
        auto [x, y] = queries[i];
        q[x].emplace_back(y, i);
        q[y].emplace_back(x, i);
    }
 
    vector<int> parent(n + 1), rank(n + 1), ancestor(n + 1);
    vector<int> state(n + 1); // 0 未访问，1 正在 DFS，2 已处理完成
    vector<int> ans(queries.size());
    iota(all(parent), 0ll);
 
    auto find = [&](auto &&self, int x) -> int
    {
        return parent[x] == x ? x : parent[x] = self(self, parent[x]);
    };
 
    auto merge = [&](int x, int y) -> void
    {
        x = find(find, x);
        y = find(find, y);
        if (x == y)
        {
            return;
        }
        if (rank[x] < rank[y])
        {
            swap(x, y);
        }
        parent[y] = x;
        if (rank[x] == rank[y])
        {
            rank[x]++;
        }
    };
 
    auto dfs = [&](auto &&self, int u, int fa) -> void
    {
        state[u] = 1;
        ancestor[u] = u;
 
        for (int nxt : adj[u])
        {
            if (nxt == fa)
            {
                continue;
            }
            self(self, nxt, u);
            merge(u, nxt);
            ancestor[find(find, u)] = u;
        }
 
        state[u] = 2;
        for (auto [other, id] : q[u])
        {
            if (state[other] == 2)
            {
                ans[id] = ancestor[find(find, other)];
            }
        }
    };
 
    dfs(dfs, root, 0);
    return ans;
}

树的重心

// ============================================================
// 树的重心
// ============================================================
// 删除重心后，剩余每个连通块的大小都不超过 n / 2。
// 一棵树最多有两个重心；如果有两个，它们一定相邻。
// adj 使用 1 下标。返回全部重心，顺序由 DFS 顺序决定。
// ============================================================
 
vector<int> get_centroids(const vector<vector<int>> &adj, int root = 1)
{
    int n = adj.size() - 1;
    vector<int> size(n + 1);
    vector<int> ans;
    int best = LLONG_MAX;
 
    auto dfs = [&](auto &&self, int u, int parent) -> void
    {
        size[u] = 1;
        int max_part = 0;
        for (int nxt : adj[u])
        {
            if (nxt == parent)
            {
                continue;
            }
            self(self, nxt, u);
            size[u] += size[nxt];
            max_part = max(max_part, size[nxt]);
        }
 
        max_part = max(max_part, n - size[u]);
        if (max_part < best)
        {
            best = max_part;
            ans.clear();
            ans.emplace_back(u);
        }
        else if (max_part == best)
        {
            ans.emplace_back(u);
        }
    };
 
    dfs(dfs, root, 0);
    return ans;
}

两次搜索求树的直径

// ============================================================
// 两次搜索求树的直径（边权要求非负）
// ============================================================
// 返回长度、两个端点以及从 left 到 right 的完整路径。
// 无权树把每条边长度视为 1；带权树使用 pair<终点, 边权>。
// 若存在负边，最远点两次搜索的结论不能直接套用，应使用树形 DP。
// ============================================================
 
struct DiameterResult
{
    int length;
    int left, right;
    vector<int> path;
};
 
DiameterResult get_diameter(const vector<vector<int>> &adj, int start = 1)
{
    int n = adj.size() - 1;
 
    auto get_farthest = [&](int source)
    {
        vector<int> parent(n + 1), dist(n + 1, -1);
        queue<int> q;
        q.push(source);
        dist[source] = 0;
 
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int nxt : adj[u])
            {
                if (nxt == parent[u])
                {
                    continue;
                }
                parent[nxt] = u;
                dist[nxt] = dist[u] + 1;
                q.push(nxt);
            }
        }
 
        int farthest = source;
        for (int i = 1; i <= n; i++)
        {
            if (dist[i] > dist[farthest])
            {
                farthest = i;
            }
        }
        return tuple<int, vector<int>, vector<int>>(farthest, parent, dist);
    };
 
    auto [left, parent1, dist1] = get_farthest(start);
    auto [right, parent, dist] = get_farthest(left);
 
    vector<int> path;
    for (int u = right; u; u = parent[u])
    {
        path.emplace_back(u);
        if (u == left)
        {
            break;
        }
    }
    reverse(all(path));
    return {dist[right], left, right, path};
}
 
DiameterResult get_diameter(const vector<vector<pair<int, int>>> &adj, int start = 1)
{
    int n = adj.size() - 1;
 
    auto get_farthest = [&](int source)
    {
        vector<int> parent(n + 1), dist(n + 1, LLONG_MIN);
        stack<int> st;
        st.push(source);
        dist[source] = 0;
 
        while (!st.empty())
        {
            int u = st.top();
            st.pop();
            for (auto [nxt, w] : adj[u])
            {
                if (nxt == parent[u])
                {
                    continue;
                }
                parent[nxt] = u;
                dist[nxt] = dist[u] + w;
                st.push(nxt);
            }
        }
 
        int farthest = source;
        for (int i = 1; i <= n; i++)
        {
            if (dist[i] > dist[farthest])
            {
                farthest = i;
            }
        }
        return tuple<int, vector<int>, vector<int>>(farthest, parent, dist);
    };
 
    auto [left, parent1, dist1] = get_farthest(start);
    auto [right, parent, dist] = get_farthest(left);
 
    vector<int> path;
    for (int u = right; u; u = parent[u])
    {
        path.emplace_back(u);
        if (u == left)
        {
            break;
        }
    }
    reverse(all(path));
    return {dist[right], left, right, path};
}

树形 DP 求直径

// ============================================================
// 树形 DP 求直径
// ============================================================
// down[u]：从 u 向子树内走的最长链。
// 对每个 u，取最大的两条子链拼起来更新直径。
// 这里返回直径长度；如果还需要端点和路径，使用 dfs diameter.txt。
// 无权树返回边数；带权版本允许非负边权。
// ============================================================
 
int tree_diameter_dp(const vector<vector<int>> &adj, int root = 1)
{
    int n = adj.size() - 1;
    vector<int> down(n + 1);
    int ans = 0;
 
    auto dfs = [&](auto &&self, int u, int parent) -> void
    {
        int first = 0, second = 0;
        for (int nxt : adj[u])
        {
            if (nxt == parent)
            {
                continue;
            }
            self(self, nxt, u);
            int cur = down[nxt] + 1;
            if (cur > first)
            {
                second = first;
                first = cur;
            }
            else if (cur > second)
            {
                second = cur;
            }
        }
        down[u] = first;
        ans = max(ans, first + second);
    };
 
    dfs(dfs, root, 0);
    return ans;
}
 
int tree_diameter_dp(const vector<vector<pair<int, int>>> &adj, int root = 1)
{
    int n = adj.size() - 1;
    vector<int> down(n + 1);
    int ans = 0;
 
    auto dfs = [&](auto &&self, int u, int parent) -> void
    {
        int first = 0, second = 0;
        for (auto [nxt, w] : adj[u])
        {
            if (nxt == parent)
            {
                continue;
            }
            self(self, nxt, u);
            int cur = down[nxt] + w;
            if (cur > first)
            {
                second = first;
                first = cur;
            }
            else if (cur > second)
            {
                second = cur;
            }
        }
        down[u] = first;
        ans = max(ans, first + second);
    };
 
    dfs(dfs, root, 0);
    return ans;
}

Dijkstra 最短路

using ll = long long;
const ll INF = (1LL << 62);
 
vector<ll> dijkstra(int n, int s,
                    const vector<vector<pair<int, int>>>& g) {
    vector<ll> dist(n + 1, INF);
    priority_queue<pair<ll, int>,
                   vector<pair<ll, int>>,
                   greater<pair<ll, int>>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (!pq.empty()) {
        auto [du, u] = pq.top();
        pq.pop();
        if (du != dist[u]) continue;
        for (auto [v, w] : g[u]) {
            if (dist[v] > du + w) {
                dist[v] = du + w;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Kruskal 最小生成树

struct Edge {
    int u, v;
    long long w;
};
 
// 依赖 DSU；不连通时返回 nullopt。
optional<long long> kruskal(int n, vector<Edge> edges) {
    sort(edges.begin(), edges.end(),
         [](const Edge& a, const Edge& b) { return a.w < b.w; });
    DSU dsu(n);
    long long ans = 0;
    int used = 0;
    for (auto [u, v, w] : edges) {
        if (dsu.merge(u, v)) {
            ans += w;
            if (++used == n - 1) break;
        }
    }
    if (used != n - 1) return nullopt;
    return ans;
}

拓扑排序

// 返回任意一个拓扑序；存在环时返回空数组。
vector<int> topo_sort(int n, const vector<vector<int>>& g) {
    vector<int> indeg(n + 1), order;
    for (int u = 1; u <= n; ++u)
        for (int v : g[u]) ++indeg[v];
 
    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) q.push(i);
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        order.push_back(u);
        for (int v : g[u])
            if (--indeg[v] == 0) q.push(v);
    }
    if ((int)order.size() != n) return {};
    return order;
}