[ZJOI2011]道馆之战 题解
题目地址:洛谷:【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;
}