3754. 【 NOI 2014 】 마법 의 숲 (LCT)

Problem
하나의 \ (n \) 개의 노드 를 지정 합 니 다. \ (m \) 변 의 무 방향 그림 은 각 변 에 두 개의 가중치 가 있 습 니 다 \ (ai, bi \).
이제 \ (1 \) 에서 출발 하여 \ (n \) 에 도착 하려 면 매번 \ (ai \ le A \) 와 \ (bi \ le B \) 의 옆 을 따라 가 야 합 니 다.
\(n\le 5*10^4,m\le 2*10^5\)
Solution
전형 적 인 LCT 문 제 는 변경 권 을 점 권 으로 하면 없어진다.
참고 로 LCT 라 는 신기 한 데이터 구 조 를 말씀 드 리 겠 습 니 다.자세 가 제한 되 어 있 기 때문에, 그 위치 분석 은 잠시 논의 하지 않 는 다.
정의.
LCT = splay + 허실 분할
각 노드 는 기껏해야 한 개의 실제 변 이 아들 에 게 연결 되 고 실제 변 이 연결 되 어 하나의 실제 사슬 을 구성 했다.
모든 실제 체인 은 하나의 splay 로 유지 하고 키 워드 는 원래 나무 에서 뿌리 노드 를 기준 으로 하 는 깊이 입 니 다.
Access
가장 중요 한 조작.Access(N) 은 \ (N \) 에서 루트 노드 까지 의 모든 노드 의 실제 변 화 를 바 꾸 는 것 으로 정의 합 니 다.
코드 에서 이 과정 으로 구현:

void Access(int x) {
    for (int y = 0; x ; y = x, x = fa[x])
        splay(x), tr[x][1] = y, update(x);
}

Makeroot
어떤 점 을 뿌리 로 정의 하고 이 과정 으로 이 루어 집 니 다.

void Makeroot(int x) {
    Access(x);
    splay(x);
    reverse(x);
}

Link，cut
쉬 워 보 여요.

void link(int x,int y) {
    Makeroot(x);
    fa[x] = y;
}

void cut(int x, int y) {
    Makeroot(x);
    Access(y);
    splay(y);
    fa[tr[y][0]] = 0, tr[y][0] = 0;
    update(y);
}

주의 하 다.rotate 의 타 법 은 이렇게 치 는 것 을 기억 해 야 한다.

void rotate(int x) {
    int y = fa[x], t = son(x);
    if (!Rt(y)) tr[fa[y]][son(y)] = x; //        ！！！
    if (tr[x][1 - t]) fa[tr[x][1 - t]] = y;
    fa[x] = fa[y], fa[y] = x, tr[y][t] = tr[x][1 - t], tr[x][1 - t] = y;
    update(y), update(x); 
}

Code

#include 

#define F(i, a, b) for (int i = a; i <= b; i ++)
#define ls tr[x][0]
#define rs tr[x][1]

const int N = 2e5 + 10;

using namespace std;

int n, m, x, y, Ans, RT;
int v[N], tr[N][2], fa[N], rev[N], d[N], pt[N], fat[N];
struct edge {
    int x, y, a, b;
    friend bool operator < (edge a, edge b) { return a.a < b.a; }
} e[N];

int son(int x) { return tr[fa[x]][1] == x; }
bool Rt(int x) { return tr[fa[x]][son(x)] ^ x; }

void reverse(int x) { swap(ls, rs), rev[x] ^= 1; }
void push(int x) {
    if (!rev[x]) return;
    reverse(ls), reverse(rs), rev[x] = 0;
}

void update(int x) {
    pt[x] = x;
    if (v[pt[ls]] > v[pt[x]]) pt[x] = pt[ls];
    if (v[pt[rs]] > v[pt[x]]) pt[x] = pt[rs];
}

void rotate(int x) {
    int y = fa[x], t = son(x);
    if (!Rt(y)) tr[fa[y]][son(y)] = x;
    if (tr[x][1 - t]) fa[tr[x][1 - t]] = y;
    fa[x] = fa[y], fa[y] = x, tr[y][t] = tr[x][1 - t], tr[x][1 - t] = y;
    update(y), update(x); 
}

void clear(int x) {
    d[++ d[0]] = x;
    while (!Rt(x)) d[++ d[0]] = x = fa[x];
    while (d[0]) push(d[d[0] --]);
}

void splay(int x) {
    clear(x);
    for (; !Rt(x); rotate(x))
        if (!Rt(fa[x])) rotate(son(x) == son(fa[x]) ? fa[x] : x);
}

void Access(int x) {
    for (int y = 0; x ; y = x, x = fa[x])
        splay(x), rs = y, update(x);
}

void Makeroot(int x) { Access(x), splay(x), reverse(x); }
void link(int x, int y) { Makeroot(x), fa[x] = y; }
void cut(int x, int y) { Makeroot(x); Access(y); splay(y); fa[tr[y][0]] = 0, tr[y][0] = 0; update(y); }

int Solve(int x, int y) {
    Makeroot(x); Access(y), splay(y);
    return pt[y];
}
int get(int x) { return !fat[x] ? x : fat[x] = get(fat[x]); }

int main() {
    scanf("%d%d", &n, &m);
    F(i, 1, m) {
        scanf("%d%d%d%d", &e[i].x, &e[i].y, &e[i].a, &e[i].b);
        if (e[i].x == e[i].y) i --, m --;
    }

    sort(e + 1, e + m + 1);

    Ans = 1e9;
    F(i, 1, m) {
        x = e[i].x, y = e[i].y, v[i + n] = e[i].b;
        int xx = get(x), yy = get(y);
        if (xx ^ yy) fat[xx] = yy; else {
            int pos = Solve(x, y);
            if (v[pos] <= e[i].b) continue;
            cut(e[pos - n].x, pos), cut(pos, e[pos - n].y);
        }
        link(x, i + n), link(i + n, y);
        if (get(1) == get(n))
            Ans = min(Ans, e[i].a + v[Solve(1, n)]);
    }
    printf("%d
", Ans == 1e9 ? - 1 : Ans);
}

다음으로 전송:https://www.cnblogs.com/Pro-king/p/10760435.html