2018年3月20日

[SPOJ-QTREE4]Query on a tree IV 题解

题目地址：洛谷：【SP2666】QTREE4 – Query on a tree IV – 洛谷、SPOJ：SPOJ.com – Problem QTREE4

SPOJ QTREE系列：

[SPOJ-QTREE]Query on a tree 题解（树链剖分）
[SPOJ-QTREE2]Query on a tree II 题解（树链剖分）
[SPOJ-PT07J]Query on a tree III 题解（主席树）
[SPOJ-QTREE3]Query on a tree again! 题解（树链剖分）
[SPOJ-QTREE4]Query on a tree IV 题解（点分治/边分治）
[SPOJ-QTREE5]Query on a tree V 题解（边分治）
[SPOJ-QTREE6]Query on a tree VI 题解（LCT）
[SPOJ-QTREE7]Query on a tree VII 题解（LCT）

题目描述

You are given a tree (an acyclic undirected connected graph) with N nodes, and nodes numbered 1,2,3…,N. Each edge has an integer value assigned to it(note that the value can be negative). Each node has a color, white or black. We define dist(a, b) as the sum of the value of the edges on the path from node a to node b.
All the nodes are white initially.
We will ask you to perfrom some instructions of the following form:

C a : change the color of node a.(from black to white or from white to black)
A : ask for the maximum dist(a, b), both of node a and node b must be white(a can be equal to b). Obviously, as long as there is a white node, the result will alway be non negative.

给一棵有边权的树，最初点全是白色的，操作：1.改变一个点的颜色（黑→白，白→黑）2.询问最远两个白点间距离。

输入输出格式

输入格式：
In the first line there is an integer N (N <= 100000)
In the next N-1 lines, the i-th line describes the i-th edge: a line with three integers a b c denotes an edge between a, b of value c (-1000 <= c <= 1000)
In the next line, there is an integer Q denotes the number of instructions (Q <= 100000)
In the next Q lines, each line contains an instruction “C a” or “A”

输出格式：
For each “A” operation, write one integer representing its result. If there is no white node in the tree, you should write “They have disappeared.”.

输入输出样例

输入样例#1：

输出样例#1：

2
2
0
They have disappeared.

题解

本题可以用点分治的做法解决，做法类似[ZJOI2007]捉迷藏题解 | KSkun’s Blog。这里介绍边分治的做法。
我们在中心边位置维护两个堆，一个表示左边子树的各个白点距离，一个表示右边子树的。单独维护每个分治结构的答案，我们可以在一个统计最大值的时候顺带把子分治结构的最大值也计算进来，这样询问的时候只需要询问根分支结构的答案即可。在加点的的过程中，记录下这个点会影响到的堆的数据。变白要把这个点放进堆里，变黑只需要打标记。而每一次更新答案的时候，从堆顶把黑点全扔掉就好。如果用数组/vector来存的话，这个更新要根据倒序，因此倒序才是分治结构从底向根的顺序。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

#include <vector>
#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'A' || c == 'C';
}

inline char readop() {
    char c;
    while(!isop(c = fgc()));
    return c;
}

const int MAXN = 200005, INF = 2e9;

int n, q, col[MAXN], ans;

struct Edge {
    int to, w, nxt;
} gra[MAXN << 1], grao[MAXN << 1];
int head[MAXN], heado[MAXN], ecnt, ecnto;

inline void addedge(int u, int v, int w) {
    gra[ecnt] = Edge {v, w, head[u]}; head[u] = ecnt++;
}

inline void addedgeo(int u, int v, int w) {
    grao[ecnto] = Edge {v, w, heado[u]}; heado[u] = ecnto++;
}

inline void rebuild(int u, int fa) {
    int ff = 0;
    for(int i = heado[u]; ~i; i = grao[i].nxt) {
        int v = grao[i].to, w = grao[i].w;
        if(v == fa) continue;
        if(!ff) {
            addedge(u, v, w);
            addedge(v, u, w);
            ff = u;
        } else {
            int k = ++n;
            col[k] = 1;
            addedge(ff, k, 0);
            addedge(k, ff, 0);
            addedge(k, v, w);
            addedge(v, k, w);
            ff = k;
        }
        rebuild(v, u);
    }
}

bool del[MAXN << 1];
int ct, ctsiz, sum;
int siz[MAXN], msz[MAXN];

inline void calsiz(int u, int fa) {
    siz[u] = 1;
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        calsiz(v, u);
        siz[u] += siz[v];
    }
}

inline void findct(int u, int fa) {
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(del[i >> 1] || v == fa) continue;
        findct(v, u);
        int vsiz = std::max(siz[v], sum - siz[v]);
        if(vsiz < ctsiz) {
            ct = i;
            ctsiz = vsiz;
        }
    }
}

struct DisData {
    int u, d;
    inline bool operator<(const DisData &rhs) const {
        return d < rhs.d;
    }
};

std::priority_queue<DisData> s[MAXN][2];
int cnt;

struct NodeData {
    int bel, side, dis;
};
std::vector<NodeData> ndata[MAXN];

inline void caldis(int u, int fa, int d, int t, int l) {
    if(!col[u]) {
        s[t][l].push(DisData {u, d}); ndata[u].push_back(NodeData {t, l, d});
    }
    for(int i = head[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to, w = gra[i].w;
        if(del[i >> 1] || v == fa) continue;
        caldis(v, u, d + w, t, l);
    }
}

int mx[MAXN], lch[MAXN], rch[MAXN], ctw[MAXN];

inline void update(int p) {
    while(!s[p][0].empty() && col[s[p][0].top().u]) s[p][0].pop();
    while(!s[p][1].empty() && col[s[p][1].top().u]) s[p][1].pop();
    if(s[p][0].empty() || s[p][1].empty()) mx[p] = 0;
    else mx[p] = s[p][0].top().d + ctw[p] + s[p][1].top().d;
    if(lch[p]) mx[p] = std::max(mx[p], mx[lch[p]]);
    if(rch[p]) mx[p] = std::max(mx[p], mx[rch[p]]);
}

inline int divide(int u) {
    calsiz(u, 0);
    ct = -1; ctsiz = INF; sum = siz[u]; findct(u, 0);
    if(ct == -1) return 0;
    int x = gra[ct].to, y = gra[ct ^ 1].to;
    del[ct >> 1] = true;
    int t = ++cnt;
    ctw[t] = gra[ct].w;
    caldis(x, 0, 0, t, 0); caldis(y, 0, 0, t, 1);
    lch[t] = divide(x); rch[t] = divide(y); 
    update(t);
    return t;
}

inline void setwhite(int u) {
    for(int i = ndata[u].size() - 1; i >= 0; i--) {
        NodeData d = ndata[u][i];
        s[d.bel][d.side].push(DisData {u, d.dis});
        update(d.bel);
    }
}

inline void setblack(int u) {
    for(int i = ndata[u].size() - 1; i >= 0; i--) {
        NodeData d = ndata[u][i];
        update(d.bel);
    }
}

int ut, vt, wt;
char op;

int main() {
    memset(head, -1, sizeof(head));
    memset(heado, -1, sizeof(heado));
    n = readint();
    int white = n;
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint(); wt = readint();
        addedgeo(ut, vt, wt);
        addedgeo(vt, ut, wt);
    }
    rebuild(1, 0);
    divide(1);
    q = readint();
    while(q--) {
        op = readop();
        if(op == 'A') {
            if(!white) {
                puts("They have disappeared.");
            } else if(white == 1) {
                puts("0");
            } else {
                printf("%d\n", mx[1]);
            }
        } else {
            ut = readint(); 
            col[ut] ^= 1;
            if(col[ut]) {
                setblack(ut);
                white--;
            } else {
                setwhite(ut);
                white++;
            }
        }
    }
    return 0;
}

Author: KSkun

Filed Under: 题解, 算法, SPOJ

Tags: 动态点分治, 可持久化, 图论, 堆, 数据结构, 树, 点分治, 边分治

边分治原理及实现

[SPOJ-QTREE5]Query on a tree V 题解

发表回复取消回复

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据。