13510번: 트리와 쿼리 1

https://www.acmicpc.net/problem/13510

HLD를 구현한다.

시간복잡도는 $O((n+m)\lg n)$

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int last[100001], idx[100001], cnt[100001], par[100001], tree[400000], c;
int n, m, u[100000], v[100000], w[100000];
vector<int> adj[100001];
void count(int h, int p) {
    for (int it : adj[h]) if (it^p) count(it, h), cnt[h] += cnt[it];
    cnt[h]++;
}
void build(int h, int p) {
    int t = 0;
    for (int it : adj[h]) if (it^p && cnt[t] < cnt[it]) t = it;
    for (int it : adj[h]) if (it^p && it^t) build(it, h);
    if (!last[h]) last[h] = h;
    if (t) last[t] = last[h], build(t, h);
    par[h] = p;
    idx[h] = ++c;
}
void update(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    if (l == r) tree[h] = x;
    else {
        update(h * 2 + 1, l, (l + r) / 2, g, x);
        update(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
        tree[h] = max(tree[h * 2 + 1], tree[h * 2 + 2]);
    }
}
int query(int h, int l, int r, int gl, int gr) {
    if (gr < l || r < gl) return 0;
    if (gl <= l&&r <= gr) return tree[h];
    return max(query(h * 2 + 1, l, (l + r) / 2, gl, gr), query(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr));
}
int lca(int x, int y) {
    int ret = 0;
    while (last[x] ^ last[y]) {
        if (cnt[last[x]] > cnt[last[y]]) swap(x, y);
        ret = max(ret, query(0, 1, n, idx[x], idx[last[x]]));
        x = par[last[x]];
    }
    if (cnt[x] > cnt[y]) swap(x, y);
    return max(ret, query(0, 1, n, idx[x], idx[y] - 1));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        scanf("%d%d%d", u + i, v + i, w + i);
        adj[u[i]].push_back(v[i]);
        adj[v[i]].push_back(u[i]);
    }
    count(1, 0);
    build(1, 0);
    for (int i = 1; i < n; i++) {
        if (par[v[i]] == u[i]) swap(u[i], v[i]);
        update(0, 1, n, idx[u[i]], w[i]);
    }
    scanf("%d", &m);
    for (int i = 0, q, x, y; i < m; i++) {
        scanf("%d%d%d", &q, &x, &y);
        if (q == 1) update(0, 1, n, idx[u[x]], y);
        else printf("%d\n", lca(x, y));
    }
    return 0;
}

1626번: 두 번째로 작은 스패닝 트리

https://www.acmicpc.net/problem/1626

MST를 이루는 간선(e1)을 하나 제거하고 그 간선과 다른 가중치의 간선(e2)으로 forest를 연결해보자. 두 번째로 작은 스패닝 트리는 (e2의 가중치) - (e1의 가중치)가 가장 작을 때 만들어 진다.

e2를 MST에 추가하면 그래프에는 정확히 하나의 사이클이 존재하고 그 사이클에 e1과 e2가 모두 존재한다. 다시 말해 MST에서 e2의 양 끝 정점을 연결하는 MST 위의 경로 중에 e1이 존재한다.

(e2의 가중치) - (e1의 가중치)의 최솟값을 구하기 위해선 MST에 없는 간선(e2)마다 트리 위의 경로 중 가중치가 해당 간선보다 작으면서 가장 큰 간선(e1)을 찾으면 된다.

이러한 문제는 LCA를 구해서 해결할 수 있는 문제로 기본적인 트릭이 잘 알려져 있다. 아래 소스에서는 sparse table을 이용하여 주어진 두 정점에 대해 LCA 및 1, 2번째 최소 가중치 간선을 $O(\lg n)$에 구할 수 있도록 구현했다. 여기서 두 개의 최소 가중치를 구하는 이유는 만약 첫 번째 최소 가중치가 e2의 가중치와 같을 경우 두 번째 가중치를 사용해야 하기 때문이다.

답은 (MST 가중치) + min( (e2의 가중치) - (e1의 가중치) )이다.

최종 시간복잡도는 $O(e\lg v)$

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct edge {
    int x, y, d;
}ed[200000];
struct st {
    int f = -1, s = -1;
    st operator+(st t) const {
        st ret = *this;
        if (ret.f^t.f) ret.s = max(ret.s, t.f);
        if (ret.f < ret.s) swap(ret.f, ret.s);
        ret.s = max(ret.s, t.s);
        return ret;
    }
}maxi[50001][16];
int v, e, par[50001], tot, dp[50001][16], lv[50001], ck[200000], cnt, res = -1;
vector<pair<int, int> > adj[50001];
int p(int x) { return x^par[x] ? par[x] = p(par[x]) : x; }
void f(int h, int p) {
    for (auto it : adj[h]) if (it.first^p) {
        dp[it.first][0] = h;
        maxi[it.first][0].f = it.second;
        for (int i = 1; i < 16; i++) {
            dp[it.first][i] = dp[dp[it.first][i - 1]][i - 1];
            maxi[it.first][i] = maxi[dp[it.first][i - 1]][i - 1] + maxi[it.first][i - 1];
        }
        lv[it.first] = lv[h] + 1;
        f(it.first, h);
    }
}
st query(int x, int y) {
    st ret;
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = 16; i--;) if (1 << i <= lv[x] - lv[y]) ret = ret + maxi[x][i], x = dp[x][i];
    if (x == y) return ret;
    for (int i = 16; i--;) if (dp[x][i] != dp[y][i]) {
        ret = ret + maxi[x][i] + maxi[y][i];
        x = dp[x][i];
        y = dp[y][i];
    }
    return ret + maxi[x][0] + maxi[y][0];
}
int main() {
    scanf("%d%d", &v, &e);
    for (int i = 0; i < e; i++) scanf("%d%d%d", &ed[i].x, &ed[i].y, &ed[i].d);
    sort(ed, ed + e, [](edge i, edge j) {return i.d < j.d; });
    for (int i = 1; i <= v; i++) par[i] = i;
    for (int i = 0; i < e; i++) {
        int ra = p(ed[i].x), rb = p(ed[i].y);
        if (ra^rb) {
            par[ra] = rb;
            adj[ed[i].x].push_back({ ed[i].y,ed[i].d });
            adj[ed[i].y].push_back({ ed[i].x,ed[i].d });
            tot += ed[i].d;
            ck[i] = 1;
            cnt++;
        }
    }
    if (cnt^v - 1) { puts("-1"); return 0; }
    f(1, 0);
    for (int i = 0; i < e; i++) if (!ck[i]) {
        st ret = query(ed[i].x, ed[i].y);
        if (ret.f^ed[i].d && (!~res || res>ed[i].d - ret.f + tot)) res = ed[i].d - ret.f + tot;
        if (~ret.s && (!~res || res>ed[i].d - ret.s + tot)) res = ed[i].d - ret.s + tot;
    }
    printf("%d", res);
    return 0;
}

3351번: 삼각 분할

https://www.acmicpc.net/problem/3351


$O(n\lg n)$

삼각형을 노드, 인접한 삼각형끼리 간선으로 연결하면 트리가 된다. 이를 rooted 트리로 만들자.
같은 색의 노드를 모두 연결하는 최소 크기의 부분 트리에 대해 해당 트리에 존재하는 모든 간선들은 절단할 수 없다.
이러한 간선들은 lca + prefix sum을 이용하여 파악할 수 있다.
부분 트리의 리프 노드에 1씩 증가시켜주고 루트에 리프 노드 개수 만큼 차감시켜준다.
이제 루트부터 dfs를 돌며 누적값을 따져보면 절단 가능 여부를 판단할 수 있다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MXN = 1e5 - 2;
pair <ll, int> p[MXN * 3 + 1];
vector<int> adj[MXN + 1], st[MXN + 3];
int n, dp[MXN + 1][17], d[MXN + 1], s[MXN + 1], r;
void f(int h, int p) {
    for (auto it : adj[h]) if (it^p) {
        dp[it][0] = h;
        for (int i = 1; i < 17; i++) dp[it][i] = dp[dp[it][i - 1]][i - 1];
        d[it] = d[h] + 1;
        f(it, h);
    }
}
int lca(int x, int y) {
    if (d[x] < d[y]) swap(x, y);
    for (int i = 16; i >= 0; i--) if (1 << i <= d[x] - d[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = 16; i >= 0; i--) if (dp[x][i] ^ dp[y][i]) x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
void g(int h, int p) {
    for (auto it : adj[h]) if (it^p) {
        g(it, h);
        r += !s[it];
        s[h] += s[it];
    }
}
int main() {
    scanf("%d", &n);
    n -= 2;
    for (int i = 1, a[3], x; i <= n; i++) {
        scanf("%d%d%d%d", a, a + 1, a + 2, &x);
        sort(a, a + 3);
        p[i] = { (ll)a[0] * n + a[1],i };
        p[i + n] = { (ll)a[0] * n + a[2],i };
        p[i + 2 * n] = { (ll)a[1] * n + a[2],i };
        st[x].push_back(i);
    }
    sort(p + 1, p + 1 + 3 * n);
    for (int i = 2; i <= 3 * n; i++) if (p[i].first == p[i - 1].first) {
        adj[p[i].second].push_back(p[i - 1].second);
        adj[p[i - 1].second].push_back(p[i].second);
    }
    f(1, 0);
    for (int i = 1; i <= n + 2; i++) {
        for (int j = 1; j < st[i].size(); j++) {
            s[st[i][0]]++;
            s[st[i][j]]++;
            s[lca(st[i][0], st[i][j])] -= 2;
        }
    }
    g(1, 0);
    printf("%d", r);
    return 0;
}

12745번: Traffic (Small)

https://www.acmicpc.net/problem/12745


dfs를 q번 돌게 했더니 시간 초과되었다.
같은 시간 복잡도에서도 상수가 작은 lca 연산으로 해결한다.

$O(nq)$

주어진 그래프를 rooted tree 로 만든다.
(x,y) 쿼리가 들어오면 x와 y를 연결하는 경로상의 간선에 카운트 해준다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 2222;
int n, q, s[MXN + 1], par[MXN + 1], dep[MXN + 1], r;
vector<int> adj[MXN + 1];
pair<int, int> t;
void f(int x) {
    for (auto it : adj[x]) if (it^par[x]) {
        par[it] = x;
        dep[it] = dep[x] + 1;
        f(it);
    }
}
void g(int x, int y) {
    s[x]++;
    pair<int, int> tp = { x,y };
    if (tp.first>tp.second) swap(tp.first, tp.second);
    if (s[x]>r || s[x] == r&&tp<t) {
        r = s[x];
        t = tp;
    }
}
void lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    while (dep[x]>dep[y]) g(x, par[x]), x = par[x];
    while (par[x] ^ par[y]) {
        g(x, par[x]);
        g(y, par[y]);
        x = par[x];
        y = par[y];
    }
    if (x^y) g(x, par[x]), g(y, par[y]);
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y; i<n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        lca(x, y);
    }
    printf("%d %d %d", t.first, t.second, r);
    return 0;
}

12746번: Traffic (Large)

https://www.acmicpc.net/problem/12746


$O((n+q)\lg n)$

주어진 그래프를 rooted tree 로 만든다.
(x,y) 쿼리가 들어오면 s[x]++, s[y]++, s[lca(x,y)]-=2를 해주고
루트를 시작점으로 dfs를 돌면서 자식의 s[]를 부모의 s[]에 누적시키면 모든 간선의 방문 수를 알 수 있다.
lca 쿼리를 O(lgn)이 되도록 구현해야 한다.

#include<cstdio>
#include<vector>
using namespace std;
const int MXN = 222222;
int n, q, dp[MXN + 1][18], dep[MXN + 1], s[MXN + 1], r;
vector<int> adj[MXN + 1];
pair<int, int> t;
void f(int x) {
    for (auto it : adj[x]) {
        if (it == dp[x][0]) continue;
        dep[it] = dep[x] + 1;
        dp[it][0] = x;
        for (int i = 1; i<18; i++) dp[it][i] = dp[dp[it][i - 1]][i - 1];
        f(it);
    }
}
void g(int x) {
    for (auto it : adj[x]) if (it^dp[x][0]) {
        g(it);
        pair<int, int> tp = { x,it };
        if (x>it) swap(tp.first, tp.second);
        if (s[it]>r || s[it] == r&&tp<t) {
            r = s[it];
            t = tp;
        }
        s[x] += s[it];
    }
}
int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
        if (dep[x] - dep[y] >= 1 << i) x = dp[x][i];
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (dp[x][i] ^ dp[y][i]) x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, x, y; i<n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1);
    while (q--) {
        int x, y;
        scanf("%d%d", &x, &y);
        s[x]++;
        s[y]++;
        s[lca(x, y)] -= 2;
    }
    g(1);
    printf("%d %d %d", t.first, t.second, r);
    return 0;
}

11438번: LCA 2

https://www.acmicpc.net/problem/11438


$O(n+m\lg n)$

LCA를 구현하자. sparse table을 이용한다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100000, LGN = 16;
int n, m;
int dp[MAX_N + 1][LGN + 1], lv[MAX_N + 1];
bool ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void dfs(int h) {
    ck[h] = true;
    for (auto it : adj[h]) {
        if (ck[it]) continue;
        lv[it] = lv[h] + 1;
        dp[it][0] = h;
        for (int i = 1; i <= LGN; i++)
            dp[it][i] = dp[dp[it][i - 1]][i - 1];
        dfs(it);
    }
}
int lca(int x, int y) {
    if (lv[x] < lv[y]) swap(x, y);
    for (int i = LGN; i >= 0; i--)
        if (1 << i <= lv[x] - lv[y]) x = dp[x][i];
    if (x == y) return x;
    for (int i = LGN; i >= 0; i--)
        if (dp[x][i] != dp[y][i])
            x = dp[x][i], y = dp[y][i];
    return dp[x][0];
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

11437번: LCA

https://www.acmicpc.net/problem/11437


$O(n+mn)$

LCA를 구현하자.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 100000;
int n, m;
int par[MAX_N + 1], lv[MAX_N + 1];
bool ck[MAX_N + 1];
vector<int> adj[MAX_N + 1];
void dfs(int h) {
    ck[h] = true;
    for (auto it : adj[h]) {
        if (ck[it]) continue;
        lv[it] = lv[h] + 1;
        par[it] = h;
        dfs(it);
    }
}
int lca(int x, int y) {
    if (lv[x] < lv[y]) swap(x, y);
    for (; lv[x] != lv[y]; x = par[x]);
    while (x != y) x = par[x], y = par[y];
    return x;
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(1);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}