题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=2325
题解
可以参考线段树动态维护最大子段和的做法。
对于线段树上每个节点 (o)，维护 (ls_{0/1}, rs_{0/1}, s_{0/1, 0/1}) 分别表示从最左边的上面/下面的格子进入最多走的方块数量，从最右边的上面/下面的格子进入最多走的方块数量，从最左边的上面/下面到最右边的上面/下面的做多走的方块数量。
然后合并的时候也类似与线段树最大字段和。(ls) 的话保留左子区间的，再和左子区间的 (s) 与右子区间的 (ls) 配合的结果取最优；(rs) 类似；(s) 的话直接把左右子区间的两个对应合并起来就可以了。
树剖的时候可以剖出来两段从上到下的结果，然后把一段取反（左右颠倒）以后类似于上面的方法合并就可以了。
时间复杂度 (O(mlog^2n))。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
#define lc o << 1
#define rc o << 1 | 1
const int N = 30000 + 7;
const int INF = 0x3f3f3f3f;
int n, m, dfc, cnt;
char a[N][3];
int dep[N], f[N], siz[N], son[N], dfn[N], pre[N], top[N];
struct Edge { int to, ne; } g[N << 1]; int head[N], tot;
inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }
inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }
inline void dfs1(int x, int fa = 0) {
dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1;
for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);
}
inline void dfs2(int x, int pa) {
dfn[x] = ++dfc, pre[dfc] = x, top[x] = pa;
if (!son[x]) return; dfs2(son[x], pa);
for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);
}
struct Node {
int ls[2], rs[2], s[2][2];
inline Node() { ls[0] = ls[1] = rs[0] = rs[1] = s[0][0] = s[0][1] = s[1][0] = s[1][1] = 0; }
inline Node(char *a) {
ls[0] = ls[1] = rs[0] = rs[1] = s[0][0] = s[0][1] = s[1][0] = s[1][1] = 0;
if (a[0]) ++ls[0], ++rs[0], s[0][0] = 1; else s[0][1] = s[0][0] = s[1][0] = -INF;
if (a[1]) ++ls[1], ++rs[1], s[1][1] = 1; else s[1][0] = s[1][1] = s[0][1] = -INF;
if (s[0][1] != -INF) s[0][1] = s[1][0] = 2;
}
} t[N << 2];
inline Node operator + (const Node &a, const Node &b) {
Node ans;
ans.ls[0] = std::max(a.ls[0], std::max(a.s[0][0] + b.ls[0], a.s[0][1] + b.ls[1]));
ans.ls[1] = std::max(a.ls[1], std::max(a.s[1][0] + b.ls[0], a.s[1][1] + b.ls[1]));
ans.rs[0] = std::max(b.rs[0], std::max(a.rs[0] + b.s[0][0], a.rs[1] + b.s[1][0]));
ans.rs[1] = std::max(b.rs[1], std::max(a.rs[0] + b.s[0][1], a.rs[1] + b.s[1][1]));
ans.s[0][0] = std::max(a.s[0][0] + b.s[0][0], a.s[0][1] + b.s[1][0]), smax(ans.s[0][0], -INF);
ans.s[0][1] = std::max(a.s[0][0] + b.s[0][1], a.s[0][1] + b.s[1][1]), smax(ans.s[0][1], -INF);
ans.s[1][0] = std::max(a.s[1][0] + b.s[0][0], a.s[1][1] + b.s[1][0]), smax(ans.s[1][0], -INF);
ans.s[1][1] = std::max(a.s[1][0] + b.s[0][1], a.s[1][1] + b.s[1][1]), smax(ans.s[1][1], -INF);
return ans;
}
inline Node operator - (const Node &a) {
Node ans = a;
std::swap(ans.ls[0], ans.rs[0]), std::swap(ans.ls[1], ans.rs[1]);
std::swap(ans.s[0][1], ans.s[1][0]);
return ans;
}
inline void build(int o, int L, int R) {
if (L == R) return t[o] = Node(a[pre[L]]), (void)0;
int M = (L + R) >> 1;
build(lc, L, M), build(rc, M + 1, R);
t[o] = t[lc] + t[rc];
return;
}
inline void qupd(int o, int L, int R, int x) {
if (L == R) return t[o] = Node(a[pre[L]]), (void)0;
int M = (L + R) >> 1;
if (x <= M) qupd(lc, L, M, x);
else qupd(rc, M + 1, R, x);
t[o] = t[lc] + t[rc];
}
inline Node qsum(int o, int L, int R, int l, int r) {
if (l <= L && R <= r) return t[o];
int M = (L + R) >> 1;
if (r <= M) return qsum(lc, L, M, l, r);
if (l > M) return qsum(rc, M + 1, R, l, r);
return qsum(lc, L, M, l, r) + qsum(rc, M + 1, R, l, r);
}
inline int qry(int x, int y) {
Node ans1, ans2;
while (top[x] != top[y]) {
if (dep[top[x]] > dep[top[y]]) {
ans1 = qsum(1, 1, n, dfn[top[x]], dfn[x]) + ans1;
x = f[top[x]];
} else {
ans2 = qsum(1, 1, n, dfn[top[y]], dfn[y]) + ans2;
y = f[top[y]];
}
}
if (dep[x] > dep[y]) ans1 = qsum(1, 1, n, dfn[y], dfn[x]) + ans1;
else ans2 = qsum(1, 1, n, dfn[x], dfn[y]) + ans2;
ans2 = -ans1 + ans2;
return std::max(ans2.ls[0], ans2.ls[1]);
}
inline void work() {
dfs1(1), dfs2(1, 1), build(1, 1, n);
for (int i = 1; i <= m; ++i) {
char opt[5];
int x, y;
scanf("%s", opt);
if (*opt == 'Q') read(x), read(y), printf("%d
", qry(x, y));
else read(x), scanf("%s", a[x]), a[x][0] = a[x][0] == '.', a[x][1] = a[x][1] == '.', qupd(1, 1, n, dfn[x]);
}
}
inline void init() {
read(n), read(m);
int x, y;
for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);
for (int i = 1; i <= n; ++i) scanf("%s", a[i]), a[i][0] = a[i][0] == '.', a[i][1] = a[i][1] == '.';
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}