Heavy Light Decomposition (2)

Bài toán

Độ phức tạp

Code này của Nguyễn Tiến Trung Kiên

#include <stdio.h>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

#define long long long

#define f1(i,n) for (int i=1; i<=n; i++)

#define f0(i,n) for (int i=0; i<n; i++)

const int oo = 0x3c3c3c3c;

#define all(a) a.begin(), a.end()

#define N 100005

int n, m, Max[4*N];

vector<int> a[N];

struct node {

    int ll, rr, id;

    node (int L, int R, int X)

        { ll=L, rr=R, id=X; }

    node left()

        { return node(ll, (ll+rr)/2, id*2); }

    node right()

        { return node((ll+rr)/2+1, rr, id*2+1); }

    void increase(int u, int Value){

        if (ll>u || u>rr) return ;

        if (ll==rr) { Max[id] += Value; return ; }

        left().increase(u, Value);

        right().increase(u, Value);

        Max[id]=max(Max[id*2], Max[id*2+1]);

    }

    int max_range(int L, int R){

        if (L>rr || ll>R || L>R) return -oo;

        if (L<=ll && rr<=R) return Max[id];

        int Max1 = left().max_range(L, R);

        int Max2 = right().max_range(L, R);

        return max(Max1, Max2);

    }

};

int Size[N], Level[N], Parent[20][N];

int IndexOf[N], Head[N], Peak=0;

void previsit(int u, int p){ // end-update Size[], Level[], Parent[0][]

    Size[u]=1;

    for (int i=0; int v=a[u][i]; i++) if (v!=p){

        Level[v]=Level[u]+1;

        Parent[0][v]=u;

        previsit(v, u);

        Size[u]+=Size[v];

    }

}

void previsit_all(){

    Level[1]=1;

    Parent[0][1]=0;

    previsit(1, 1);

    f1(k,19) f1(i,n) Parent[k][i]=Parent[k-1][Parent[k-1][i]];

}

bool as_size(int x, int y)

    { return Size[x]>Size[y]; }

void visit(int u, int p){ // end-update a[], IndexOf[], Head[]

    a[u].erase(remove(all(a[u]), p), a[u].end());

    sort(a[u].begin(), --a[u].end(), as_size);

    for (int i=0; int v=a[u][i]; i++) {

        IndexOf[v]=++Peak;

        Head[v]=(i==0 ? Head[u] : v);

        visit(v, u);

    }

}

void visit_all(){

    IndexOf[1]=++Peak;

    Head[1]=1;

    visit(1, 1);

}

int lca(int x, int y){

    #define k(x) Parent[k][x]

    for (int k=19; k>=0; k--) if (Level[k(x)]>=Level[y]) x=k(x);

    for (int k=19; k>=0; k--) if (Level[k(y)]>=Level[x]) y=k(y);

    for (int k=19; k>=0; k--) if (k(x)!=k(y)) { x=k(x), y=k(y); }

    while (x!=y) { x=Parent[0][x], y=Parent[0][y]; }

    return x;

}

int max_path(int u, int p){

    int Max=-oo;

    while (Level[Head[u]] >= Level[p]) {

        Max = max(Max, node(1,Peak,1).max_range(IndexOf[Head[u]], IndexOf[u]));

        u=Parent[0][Head[u]];

    }

    Max = max(Max, node(1,Peak,1).max_range(IndexOf[p], IndexOf[u]));

    return Max;

}

main(){

    scanf("%d", &n);

    f1(i,n-1) {

        int x, y;

        scanf("%d%d", &x, &y);

        a[x].push_back(y);

        a[y].push_back(x);

    }

    f1(i,n) a[i].push_back(0);

    previsit_all();

    visit_all();

    scanf("%d", &m);

    f1(i,m){

        char c; int x, y;

        scanf(" %c%d%d", &c, &x, &y);

        if (c=='I') node(1,Peak,1).increase(IndexOf[x], y);

        if (c=='G') {

            int p=lca(x, y);

            printf("%d\n", max(max_path(x,p), max_path(y,p)));

        }

    }

}

Nhận xét

Tham khảo

http://acm.timus.ru/problem.aspx?space=1&num=1553