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;
}