题目地址：洛谷：【P4679】[ZJOI2011]道馆之战 – 洛谷、BZOJ：Problem 2325. — [ZJOI2011]道馆之战

题目描述

馆主为了加大难度，将道馆分成了n个房间，每个房间中是两个冰块或障碍，表示一列冰地。任意两个房间之间均有且仅有一条路径相连，即这n个房间构成一个树状结构。每个房间分成了A和B两个区域，每一区域都是一个薄冰块或者障碍物。每次只能移动到相邻房间的同一类区域(即若你现在在这个房间的A区域，那么你只能移动到相邻房间的A区域)或这个房间的另一区域。现在挑战者从房间u出发，馆主在房间v，那么挑战者只能朝接近馆主所在房间的方向过去。一开始挑战者可以在房间u的任意一个冰块区域内。如果挑战者踩过的冰块数达到了最大值(即没有一种方案踩过的冰块数更多了)，那么当挑战者走到最后一个冰块上时，他会被瞬间传送到馆主面前与馆主进行道馆战。自从馆主修改规则后已经经过了m天，每天要么是有一个挑战者来进行挑战，要么就是馆主将某个房间进行了修改。对于每个来的挑战者，你需要计算出他若要和馆主进行战斗需要经过的冰块数。

输入输出格式

输入格式：
第一行包含两个正整数n和m。第2行到第n行，每行包含两个正整数x和y，表示一条连接房间x和房间y的边。房间编
号为1…n。接下来n行，每行包含两个字符。第n + k行表示房间k的两个区域，第一个字符为A区域，第二个字符为
B区域。其中“.”(ASCII码为46)表示是薄冰块，“#”(ASCII码为35)表示是障碍物。最后的m行，每行一个操作：
C u s：将房间u里的两个区域修改为s。
Q u v：询问挑战者在房间u，馆主在房间v时，挑战者能与馆主进行挑战需要踩的冰块数。如果房间u的两个区域
都是障碍物，那么输出0。
N≤ 30 000
M ≤ 80 000

输出格式：
包含若干行，每行一个整数。即对于输入中的每个询问，依次输出一个答案。

输入输出样例

输入样例#1：

5 3
1 2
2 3
2 4
1 5
.#
..
#.
.#
..
Q 5 3
C 1 ##
Q 4 5

输出样例#1：

6
3

题解

链上信息用树剖总是没错的，套个线段树。接下来的内容只研究区间信息和合并。
首先我们要求一个点出发能走的最远距离，自然要把这个答案记起来，那么用far[2][2]表示区间左1左2右1右2开始走最远距离（这里其实有点像[SHOI2008]堵塞的交通 题解 | KSkun’s Blog）。为了区间合并，我们还要记下dis[2][2]表示区间左边两个区域到右边两个区域分别的最远路径长度。
初始的时候，如果不能走，可以以-INF为初值，这样后面取max比较好办。以长度为1的区间开始设置初始值，设置的部分比较容易理解可以看代码或者类比SHOI毒瘤题。合并的时候，dis数组计算应当枚举跨越mid时是从1区域还是2区域通行的，far数组应当对跨越mid和不跨越mid分别统计。这个图示与SHOI毒瘤题其实长得差不多，可以参考那个题，结合代码理解。
查询的时候，可能要翻转其中的一半答案再合并成最后的答案。swap的时候可以考虑记下来起点在当前的哪一端。
题解参考了【BZOJ-2325】道馆之战 树链剖分 + 线段树 – DaD3zZ – 博客园，感谢原作者。

代码

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

#include <vector>
#include <algorithm>

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;
    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 isstatus(char c) {
    return c == '.' || c == '#';
}

inline bool readstatus() {
    char c;
    while(!isstatus(c = fgc()));
    return c == '.';
}

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

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

const int MAXN = 300005, INF = 1e9;

int n, m, ut, vt;
char op;
bool w[MAXN][2];
int fa[MAXN], siz[MAXN], son[MAXN], dfn[MAXN], ptn[MAXN], top[MAXN], dep[MAXN], cnt;
std::vector<int> gra[MAXN];

inline void addedge(int u, int v) {
    gra[u].push_back(v);
    gra[v].push_back(u);
}

inline void dfs1(int u) {
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa[u]) continue;
        dep[v] = dep[u] + 1;
        fa[v] = u;
        dfs1(v);
        siz[u] += siz[v] + 1;
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

inline void dfs2(int u, int tp) {
    top[u] = tp;
    dfn[u] = ++cnt;
    ptn[dfn[u]] = u;
    if(son[u]) dfs2(son[u], tp);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == son[u] || v == fa[u]) continue;
        dfs2(v, v);
    }
}

struct Node {
    int dis[2][2], far[2][2];
} sgt[MAXN << 2];

inline void merge(Node &rt, Node ls, Node rs) {
    rt.dis[0][0] = std::max(std::max(ls.dis[0][0] + rs.dis[0][0], ls.dis[0][1] + rs.dis[1][0]), -INF);
    rt.dis[0][1] = std::max(std::max(ls.dis[0][0] + rs.dis[0][1], ls.dis[0][1] + rs.dis[1][1]), -INF);
    rt.dis[1][0] = std::max(std::max(ls.dis[1][0] + rs.dis[0][0], ls.dis[1][1] + rs.dis[1][0]), -INF);
    rt.dis[1][1] = std::max(std::max(ls.dis[1][0] + rs.dis[0][1], ls.dis[1][1] + rs.dis[1][1]), -INF);
    rt.far[0][0] = std::max(ls.far[0][0], std::max(ls.dis[0][0] + rs.far[0][0], ls.dis[0][1] + rs.far[0][1]));
    rt.far[0][1] = std::max(ls.far[0][1], std::max(ls.dis[1][0] + rs.far[0][0], ls.dis[1][1] + rs.far[0][1]));
    rt.far[1][0] = std::max(rs.far[1][0], std::max(rs.dis[0][0] + ls.far[1][0], rs.dis[1][0] + ls.far[1][1]));
    rt.far[1][1] = std::max(rs.far[1][1], std::max(rs.dis[0][1] + ls.far[1][0], rs.dis[1][1] + ls.far[1][1]));
}

inline void reverse(Node &x) {
    std::swap(x.dis[0][1], x.dis[1][0]);
    std::swap(x.far[0][0], x.far[1][0]);
    std::swap(x.far[0][1], x.far[1][1]);
}

inline void build(int o, int l, int r) {
    if(l == r) {
        sgt[o].dis[0][0] = w[ptn[l]][0] ? 1 : -INF;
        sgt[o].far[0][0] = sgt[o].far[1][0] = w[ptn[l]][0];
        sgt[o].dis[1][1] = w[ptn[l]][1] ? 1 : -INF;
        sgt[o].far[0][1] = sgt[o].far[1][1] = w[ptn[l]][1];
        if(w[ptn[l]][0] && w[ptn[l]][1]) {
            sgt[o].far[0][0] = sgt[o].far[0][1] = sgt[o].far[1][0] = sgt[o].far[1][1] = 
                sgt[o].dis[0][1] = sgt[o].dis[1][0] = 2;
        } else {
            sgt[o].dis[0][1] = sgt[o].dis[1][0] = -INF;
        }
        return;
    }
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    build(lch, l, mid);
    build(rch, mid + 1, r);
    merge(sgt[o], sgt[lch], sgt[rch]);
}

inline void modify(int o, int l, int r, int x) {
    if(l == r) {
        sgt[o].dis[0][0] = w[ptn[l]][0] ? 1 : -INF;
        sgt[o].far[0][0] = sgt[o].far[1][0] = w[ptn[l]][0];
        sgt[o].dis[1][1] = w[ptn[l]][1] ? 1 : -INF;
        sgt[o].far[0][1] = sgt[o].far[1][1] = w[ptn[l]][1];
        if(w[ptn[l]][0] && w[ptn[l]][1]) {
            sgt[o].far[0][0] = sgt[o].far[0][1] = sgt[o].far[1][0] = sgt[o].far[1][1] = 
                sgt[o].dis[0][1] = sgt[o].dis[1][0] = 2;
        } else {
            sgt[o].dis[0][1] = sgt[o].dis[1][0] = -INF;
        }
        return;
    }
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(x <= mid) modify(lch, l, mid, x);
    else modify(rch, mid + 1, r, x);
    merge(sgt[o], sgt[lch], sgt[rch]);
}

inline Node query(int o, int l, int r, int ll, int rr) {
    if(l == ll && r == rr) {
        return sgt[o];
    }
    int mid = (l + r) >> 1, lch = o << 1, rch = (o << 1) | 1;
    if(rr <= mid) {
        return query(lch, l, mid, ll, rr);
    } else if(ll > mid) {
        return query(rch, mid + 1, r, ll, rr);
    } else {
        Node ls = query(lch, l, mid, ll, mid), rs = query(rch, mid + 1, r, mid + 1, rr), res;
        merge(res, ls, rs);
        return res;
    }
}

inline int query(int u, int v) {
    Node su, sv, t, t1;
    bool fu = false, fv = false, iu = true;
    int tu = top[u], tv = top[v];
    while(tu != tv) {
        if(dep[tu] > dep[tv]) {
            std::swap(tu, tv);
            std::swap(u, v);
            std::swap(su, sv);
            std::swap(fu, fv);
            iu ^= 1;
        }
        t = query(1, 1, n, dfn[tv], dfn[v]);
        if(fv) merge(t1, t, sv), sv = t1; else sv = t, fv = true;
        v = fa[tv];
        tv = top[v];
    }
    if(dep[u] > dep[v]) {
        std::swap(u, v);
        std::swap(su, sv);
        std::swap(fu, fv);
        iu ^= 1;
    }
    t = query(1, 1, n, dfn[u], dfn[v]);
    if(fv) merge(t1, t, sv), sv = t1; else sv = t, fv = true;
    if(fu) reverse(su), merge(t1, su, sv); else t1 = sv;
    return std::max(t1.far[!iu][0], t1.far[!iu][1]);
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i < n; i++) {
        ut = readint(); vt = readint();
        addedge(ut, vt);
    }
    for(int i = 1; i <= n; i++) {
        w[i][0] = readstatus();
        w[i][1] = readstatus();
    }
    dfs1(1);
    dfs2(1, 1);
    build(1, 1, n);
    while(m--) {
        op = readop();
        if(op == 'Q') {
            ut = readint(); vt = readint();
            printf("%d\n", query(ut, vt));
        }
        if(op == 'C') {
            ut = readint(); w[ut][0] = readstatus(); w[ut][1] = readstatus();
            modify(1, 1, n, dfn[ut]);
        }
    }
    return 0;
}