2016年8月9日 星期二

樹鍊剖分模板

/*
    架構來自卦長的模板庫
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int MAXN = 100001;
const int MAXM = 100001;
const int INF = 1e9;

typedef pair<int, int> E;
#define t first
#define d second

vector<E> v[MAXN], u[MAXN];
int sz[MAXN], max_son[MAXN], dep[MAXN], pa[MAXN];
int link_top[MAXN], link[MAXN], cnt;

void find_max_son(int x, int par) {
    sz[x] = 1;
    max_son[x] = -1;

    for (E e: v[x]) {
        int t = e.t;
        if ( t == par ) continue;

        dep[t] = dep[x]+1;
        pa[t] = x;
        find_max_son(t, x);
        sz[x] += sz[t];

        if ( max_son[x] == -1 || sz[t] > sz[max_son[x] ] )
            max_son[x] = t;
    }
}

void build_link(int x, int par, int top) {
    link[x] = ++cnt;
    link_top[x] = top;

    if (max_son[x] == -1) return;
    build_link(max_son[x], x, top);

    for (E e: v[x]) {
        int t = e.t;
        if ( t == max_son[x] || t == par ) continue;
        build_link(t, x, t);
    }
}

inline int find_lca(int a, int b) {
    int ta = link_top[a], tb = link_top[b];

    while (ta != tb) {
        if ( dep[ta] < dep[tb] ) {
            swap(ta, tb);
            swap(a, b);
        }

        ta = link_top[a=pa[ta]];
    }

    return dep[a]<dep[b]?a:b;
}

struct Node {
    Node *l, *r;
    int num;

    Node():l(NULL),r(NULL),num(INF){}
};

Node mem[MAXN*2]; int m;

Node *get_node() { return &(mem[m++] = Node()); }

Node *root;

Node *build(int L, int R) {
    Node *O = get_node();

    if ( L+1 != R ) {
        O->l = build(L, (L+R)/2);
        O->r = build((L+R)/2, R);
    }

    return O;
}

void add(Node *O, int L, int R, int A, int B, int x) {
    if ( B <= L || R <= A ) return;
    else if ( A <= L && R <= B ) O->num = min(O->num, x);
    else {
        add(O->l, L, (L+R)/2, A, B, x);
        add(O->r, (L+R)/2, R, A, B, x);
    }
}

int N, M;

inline void process(int a, int b, int x) {
    int ta = link_top[a], tb = link_top[b];

    while (ta != tb) {
        if ( dep[ta] < dep[tb] ) {
            swap(ta, tb);
            swap(a, b);
        }

        add(root, 1, N+1, link[ta], link[a]+1, x);
        ta = link_top[a=pa[ta]];
    }

    if ( dep[a] > dep[b] ) swap(a, b);

    add(root, 1, N+1, link[a]+1, link[b]+1, x);
}

int num[MAXN];

void DFS(int x, int par) {
    for (E e: v[x]) {
        int t = e.t, d = e.d;
        if ( t == par ) continue;
        num[t] = d;
        DFS(t, x);
    }
}

int ans;

void cal(Node *O, int L, int R, int x) {

    x = min(x, O->num);

    if ( L+1 == R ) {
        if ( x != INF ) ans += num[L]-x;
    } else {
        cal(O->l, L, (L+R)/2, x);
        cal(O->r, (L+R)/2, R, x);
    }
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        cnt = 0;
        m = 0;

        scanf("%d %d", &N, &M);

        root = build(1, N+1);

        for (int Mi = 0; Mi < M; Mi++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);

            if (Mi < N-1) {
                v[a].emplace_back(b, c);
                v[b].emplace_back(a, c);
            }

            u[a].emplace_back(b, c);
            u[b].emplace_back(a, c);
        }

        find_max_son(1, 1);
        build_link(1, 1, 1);



        for (int Ni = 1; Ni <= N; Ni++)
            for (E e: u[Ni]) {
                if ( Ni < e.t )
                    process(Ni, e.t, e.d);
            }

        ans = 0;

        DFS(1, 1);
        cal(root, 1, N+1, INF);

        printf("%d\n", ans);

        for (int Ni = 1; Ni <= N; Ni++)
            v[Ni].clear(), u[Ni].clear();
    }
}

沒有留言:

張貼留言