2 条题解

  • 1
    @ 2023-1-18 11:53:59

    最近公共祖先【模板题】

    倍增

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
const int MAXM = 500000;
int n, q, root;          // 点数、询问个数、根节点
vector<int> e[MAXN + 5]; // 存树
int fa[MAXN + 5];
int maxDep, dep[MAXN + 5];
void dfs(int u, int father)
{
    fa[u] = father;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == father)
            continue;
        dep[v] = dep[u] + 1;
        maxDep = max(maxDep, dep[v]);
        dfs(v, u);
    }
}
int lg2[MAXN + 5]; // 替代 log2(i)
int dp[MAXN][35];  // i号点的 2^j 层祖先
int lca(int u, int v)
{
    if (dep[u] > dep[v])
        swap(u, v); // 让u的高度不低于v
    if (u == v)
        return u;
    // 把 v 提到与 u 同样高度
    for (int j = lg2[n]; j >= 0; j--)
        if ((1 << j) <= dep[v] - dep[u])
        {
            v = dp[v][j];
        }
    if (u == v)
        return u;
    // 找lca
    for (int j = lg2[n]; j >= 0; j--)
        if (dp[v][j] != dp[u][j])
        {
            v = dp[v][j],
            u = dp[u][j];
        }
    return dp[u][0];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //  输入
    cin >> n >> q >> root;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 预处理：最大层数 maxDep、每个点的深度、记录父节点、log2[]、dp数组
    dep[root] = 1;
    maxDep = 1;
    dfs(root, 0);
    lg2[1] = 0;
    for (int i = 2; i <= n; i++)
        // i == 2^(log2(i-1)+1)
        if (i == (1 << (lg2[i - 1] + 1)))
            lg2[i] = lg2[i - 1] + 1;
        else
            lg2[i] = lg2[i - 1];
    for (int j = 0; j <= lg2[n]; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            // 求解 dp[i][j]
            if (j == 0)
                dp[i][j] = fa[i];
            else
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    // q 次询问
    while (q--)
    {
        int u, v;
        cin >> u >> v; // 求 lca(u,v)
        cout << lca(u, v) << "\n";
    }
    return 0;
}

    欧拉序+st表

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
const int MAXM = 1000000;
// 存图
int n, m, s; // 点数、边数、根节点
vector<int> e[MAXN + 5];
// dfs每个点的深度
int dep[MAXN * 2 + 5];
// 欧拉序：euler[1]~euler[len]
int len;
int euler[MAXN * 2 + 5]; // 最多2n-1个点 dfs每个点的编号
int pos[MAXN + 5];       // 每个编号第一次出现位置
// rmq
int l2[MAXN * 2 + 5];       // log2(i)
int rmqd[MAXN * 2 + 5][30]; // euler[i] 开始的 2^j 个数的对应深度最小值
int rmqa[MAXN * 2 + 5][30]; // 深度最小值的编号

void dfs(int u, int fa)
{
    euler[++len] = u;
    pos[u] = len;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        euler[++len] = u;
    }
}

void rmqinit()
{
    l2[0] = -1;
    for (int i = 1; i <= len; i++)
    {
        l2[i] = l2[i - 1];
        if ((1 << (l2[i] + 1)) == i)
            l2[i]++;
        rmqa[i][0] = euler[i];
        rmqd[i][0] = dep[euler[i]];
    }
    for (int j = 1; j <= l2[len]; j++)
    {
        for (int i = 1; i <= len - (1 << j) + 1; i++)
        {
            if (rmqd[i][j - 1] < rmqd[i + (1 << (j - 1))][j - 1])
            {
                rmqd[i][j] = rmqd[i][j - 1];
                rmqa[i][j] = rmqa[i][j - 1];
            }
            else
            {
                rmqd[i][j] = rmqd[i + (1 << (j - 1))][j - 1];
                rmqa[i][j] = rmqa[i + (1 << (j - 1))][j - 1];
            }
        }
    }
}

int query(int l, int r)
{
    l = pos[l];
    r = pos[r];
    if (l > r)
        swap(l, r);
    int k = l2[r - l + 1];
    if (rmqd[l][k] < rmqd[r - (1 << k) + 1][k])
        return rmqa[l][k];
    else
        return rmqa[r - (1 << k) + 1][k];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    // 构建欧拉序
    len = 0;
    dep[s] = 1;
    dfs(s, 0);
    // rmq初始化
    rmqinit();
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        cout << query(l, r) << "\n";
    }
    return 0;
}

    tarjan(离线+并查集)

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
const int MAXM = 1000000;
int n, m, s;
vector<int> e[MAXN + 5];
//(v, 问题 id)
vector<pair<int, int> > ask[MAXN + 5];
int ans[MAXM + 5]; // 问题 id 为 i 的问题答案

// 每个点是否搜过了
bool vis[MAXN + 5];
// 并查集
int fa[MAXN + 5];
int findFa(int x)
{
    if (fa[x] == x)
        return x;
    else
        return fa[x] = findFa(fa[x]);
}
void dfs(int u, int from)
{
    for (int i = 0; i < ask[u].size(); i++)
        if (vis[ask[u][i].first])
            ans[ask[u][i].second] = findFa(ask[u][i].first);
    vis[u] = true;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == from)
            continue;
        dfs(v, u);
        fa[v] = u;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    memset(ans, 0, sizeof(ans));
    // 读询问
    for (int i = 1; i <= m; i++)
    {
        int u, v, id;
        cin >> u >> v;
        id = i;
        if (u == v)
            ans[i] = u;
        else
        {
            ask[u].push_back(make_pair(v, id));
            ask[v].push_back(make_pair(u, id));
        }
    }
    // tarjan
    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
        vis[i] = false;
    }
    dfs(s, 0);
    for (int i = 1; i <= m; i++)
        cout << ans[i] << "\n";
    return 0;
}

    树链剖分

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000 + 5;
int n, m, s;
vector<int> e[MAXN];
//每个点的：父节点、深度、大小、重子节点
int fa[MAXN], dep[MAXN], siz[MAXN], hson[MAXN];
void dfs_build(int u, int fat)
{
    hson[u] = 0;
    siz[hson[u]] = 0;
    siz[u] = 1;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fat)
            continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs_build(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hson[u]])
            hson[u] = v;
    }
}
//每个点的：所在链的链顶、重边优先的 dfs 序、dfs序对应的节点编号
int tot, top[MAXN], dfn[MAXN], rnk[MAXN];
void dfs_div(int u, int fa)
{
    dfn[u] = ++tot;
    rnk[tot] = u;
    if (hson[u])
    {
        top[hson[u]] = top[u];
        dfs_div(hson[u], u);
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            if (v == fa || v == hson[u])
                continue;
            top[v] = v;
            dfs_div(v, u);
        }
    }
}
int lca(int u, int v)
{
    while (top[u] != top[v])
    {
        if (dep[top[u]] > dep[top[v]])
            u = fa[top[u]];
        else
            v = fa[top[v]];
    }
    return dep[u] > dep[v] ? v : u;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> s;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[s] = 1;
    fa[s] = 0;
    dfs_build(s, 0);
    tot = 0;
    top[s] = s;
    dfs_div(s, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}
    • 0
      @ 2023-1-29 14:49:07

      次小生成树

      严格次小生成树

      #include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500000;
const int MAXM = 500000;
// 传入两个最大次大值，返回四个数的最大次大值
pair<int, int> getMaxW(pair<int, int> a, pair<int, int> b)
{
    if (a.first == b.first)
        return make_pair(a.first, max(a.second, b.second));
    if (a.first > b.first)
        return make_pair(a.first, max(a.second, b.first));
    if (a.first < b.first)
        return make_pair(b.first, max(a.first, b.second));
}
//-----------封装LCA
struct LCA
{
    int n, root;             // 点数、询问个数、根节点
    vector<int> e[MAXN + 5]; // 存树
    int fa[MAXN + 5];
    int maxDep, dep[MAXN + 5];
    int lg2[MAXN + 5];             // 替代 log2(i)
    int dp[MAXN][35];              // i号点的 2^j 层祖先
    vector<int> ew[MAXN + 5];      // 树的边权 -----
    pair<int, int> maxW[MAXN][35]; // i号点的 2^j 层最大次大边权-----
    // 图的初始化
    void init(int _n, int _root)
    {
        n = _n;
        root = _root;
        for (int i = 1; i <= n; i++)
            e[i].clear();
    }
    // 加边
    void addEdge(int u, int v, int w)
    {
        e[u].push_back(v);
        e[v].push_back(u);
        ew[u].push_back(w); //-----
        ew[v].push_back(w); //-----
    }
    // dfs 得到父子关系、深度
    void dfs(int u, int father)
    {
        fa[u] = father;
        for (int i = 0; i < e[u].size(); i++)
        {
            int v = e[u][i];
            int w = ew[u][i]; //-----
            if (v == father)
                continue;
            dep[v] = dep[u] + 1;
            maxW[v][0] = make_pair(w, -1); //------
            maxDep = max(maxDep, dep[v]);
            dfs(v, u);
        }
    }
    // lca 的初始化
    void init_lca()
    {
        // 预处理：最大层数 maxDep、每个点的深度、记录父节点、log2[]、dp数组
        dep[root] = 1;
        maxDep = 1;
        dfs(root, 0);
        lg2[1] = 0;
        for (int i = 2; i <= n; i++)
            // i == 2^(log2(i-1)+1)
            if (i == (1 << (lg2[i - 1] + 1)))
                lg2[i] = lg2[i - 1] + 1;
            else
                lg2[i] = lg2[i - 1];
        for (int j = 0; j <= lg2[n]; j++)
        {
            for (int i = 1; i <= n; i++)
            {
                // 求解 dp[i][j]
                if (j == 0)
                    dp[i][j] = fa[i];
                else
                    dp[i][j] = dp[dp[i][j - 1]][j - 1];
                // 求解 maxW[i][j]
                if (j > 0)
                    maxW[i][j] = getMaxW(maxW[i][j - 1],
                                         maxW[dp[i][j - 1]][j - 1]);
            }
        }
    }
    // 查询两个点的lca
    int lca(int u, int v)
    {
        if (dep[u] > dep[v])
            swap(u, v); // 让u的高度不低于v
        if (u == v)
            return u;
        // 把 v 提到与 u 同样高度
        for (int j = lg2[n]; j >= 0; j--)
            if ((1 << j) <= dep[v] - dep[u])
            {
                v = dp[v][j];
            }
        if (u == v)
            return u;
        // 找lca
        for (int j = lg2[n]; j >= 0; j--)
            if (dp[v][j] != dp[u][j])
            {
                v = dp[v][j],
                u = dp[u][j];
            }
        return dp[u][0];
    }
    pair<int, int> queryMaxW(int u, int v)
    {
        int uv = lca(u, v);
        pair<int, int> res = make_pair(-1, -1);
        // 把 u 提到与 uv 同样高度
        for (int j = lg2[n]; j >= 0; j--)
            if ((1 << j) <= dep[u] - dep[uv])
            {
                res = getMaxW(res, maxW[u][j]);
                u = dp[u][j];
            }
        // 把 v 提到与 uv 同样高度
        for (int j = lg2[n]; j >= 0; j--)
            if ((1 << j) <= dep[v] - dep[uv])
            {
                res = getMaxW(res, maxW[v][j]);
                v = dp[v][j];
            }
        return res;
    }
} lca;
//-----------封装Kruskal
struct kEdge
{
    int u, v, w;
    bool cho; // 是否被选中了
};
bool operator<(const kEdge &a, const kEdge &b)
{
    return a.w < b.w;
}
struct Kruskal
{
    int n, m, ans;
    vector<kEdge> e; // 存所有的边
    int fa[MAXN + 5];
    int findFa(int x)
    {
        if (x == fa[x])
            return x;
        return fa[x] = findFa(fa[x]);
    }
    void init(int _n, int _m)
    {
        n = _n;
        m = _m;
        ans = 0;
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }
    void addEdge(int u, int v, int w)
    {
        e.push_back((kEdge){u, v, w, false});
    }
    void run()
    {
        sort(e.begin(), e.end());
        for (int i = 0; i < e.size(); i++)
        {
            int u = e[i].u;
            int v = e[i].v;
            int w = e[i].w;
            int fU = findFa(u);
            int fV = findFa(v);
            if (fU == fV)
                continue;
            e[i].cho = true; // 这条边被选择了
            ans += e[i].w;
            fa[fU] = fV;
        }
    }
} kruskal;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    kruskal.init(n, m);
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        kruskal.addEdge(u, v, w);
    }
    kruskal.run();
    lca.init(n, 1);
    for (int i = 0; i < kruskal.e.size(); i++)
        if (kruskal.e[i].cho)
            lca.addEdge(kruskal.e[i].u, kruskal.e[i].v, kruskal.e[i].w);
    lca.init_lca();

    int ans = 1e18;
    for (int i = 0; i < kruskal.e.size(); i++)
        if (!kruskal.e[i].cho)
        {
            pair<int, int> maxW = lca.queryMaxW(kruskal.e[i].u, kruskal.e[i].v);
            int m1 = maxW.first;
            int m2 = maxW.second;
            if (m1 == kruskal.e[i].w && m2 != -1)
                ans = min(ans, kruskal.ans - m2 + kruskal.e[i].w);
            else if (m1 != kruskal.e[i].w && m1 != -1)
                ans = min(ans, kruskal.ans - m1 + kruskal.e[i].w);
        }
    cout << ans << "\n";
    return 0;
}
      • 1

      最近公共祖先 - 扩展题单

      信息

      ID
      1211
      时间
      1000ms
      内存
      256MiB
      难度
      3
      标签
      递交数
      22
      已通过
      20
      上传者
      1. 评测队列
      2. 服务状态
      3. 兼容模式
      4. 主题
      2. 陕ICP备2022006801号-1
      3. Worker 0, 10ms
      4. Powered by Hydro v4.14.1 Community, Modified by 33DAI