n个结点的不带权的无根树, 每个结点或黑或白, 初始全黑. q个操作: - 切换结点i的颜色 - 查询黑点之间的最远距离
只有一个黑点输出0, 没有黑点输出-1. (n≤10^5, m≤5*10^5) Po姐说这是树分治的题 (以前总觉得树分治不能解决多次询问), 于是就yy了一发. 每个点记录一下它依次被哪些重心所分割, 到这些重心的距离, set维护每个重心 (其实所有点都会成为重心) 所在子树所有黑点的深度, 再对每个重心开个set维护每棵子树的最大深度. 然后发现不支持黑切换为白, 不好写, 还常数巨大. 想再对每个重心开个set维护每棵子树的答案, 无济于事......
看了Po姐的题解, 大致思路是对的, 为了好写还得加以提炼. 忽视了一个事实: 所有子树的最大深度+次大深度=经过该重心的最远距离. 重新叙述如下:
分治的时候, 从一个重心到子树的重心, 这个过程中形成了另一个树形结构, 它的深度为
这种 "动态树分治" 支持边加权, 对于本题这种特殊情况有更简单且时间复杂度更优的算法.
[ a [ b [ c [ d ] [ e ] ] [ f ] ] [ g [ h ] [ i ] ] ] <- 像这样的一个东西叫树的括号序列 (DFS序). 为了方便叙述, 这里把结点的标识符也看作序列的一部分.
树的括号序列有这样一个性质: 去掉匹配的括号后, 两点之间]和[的数目之和等于两点之间的距离. 本问题中, 我们只关心距离, 所以一段括号序列可以仅用两个量刻画: 抵消后, ]的数目和[的数目, 设为(a,b), 记|(a,b)| = a+b.
两段相邻的括号序列是可以合并的,
(a1, b1) + (a2, b2) = (a1 + a2 - min{b1, a2}, b1 + b2 - min{a1, a2})
|(a1, b1) + (a2, b2)| = a1 + b2 + |b1 - a2| = max{(a1 + b1) + (b2 - a2), (a1 - b1) + (b2 + a2)}尝试用线段树维护某一区间的子区间的|(a,b)|的最大值. 如果该子区间跨越了区间的中点, 由于(a1 + b1), (b2 - a2)相互独立, 分别取它们的最大值; (a1 - b1)和(b2 + a2)同理.
对每个区间维护以下量:
a 匹配的括号抵消后, ] 的数目
b 匹配的括号抵消后, [ 的数目
d 子区间 |(a,b)| 的最大值, 且该子区间左右是黑点
pre_sum 前缀区间 (a + b) 的最大值, 且黑点跟在该区间后面
pre_diff 前缀区间 (b - a) 的最大值, 且黑点跟在该区间后面
suf_sum 后缀区间 (a + b) 的最大值, 且黑点跟在该区间前面
suf_diff 后缀区间 (a - b) 的最大值, 且黑点跟在该区间前面叶子结点, ], [赋值(1, 0, -inf, -inf, -inf, -inf, -inf), (0, 1, -inf, -inf, -inf, -inf, -inf); 黑点赋值(0, 0, -inf, 0, 0, 0, 0); 白点赋值(0, 0, -inf, -inf, -inf, -inf, -inf). 这样就满足了黑白点的限制, 虽然正确性不那么好说明......
我目前只实现了这种做法的代码.
#define BRACKET(a, b) (Data){a, b, -inf, -inf, -inf, -inf, -inf}
#define BLACK (Data){0, 0, -inf, 0, 0, 0, 0}
#define WHITE BRACKET(0, 0)
const int inf = 1e8, N = 1e5;
inline int check_inf(int x)
{
return x < -1e7 ? -inf : x;
}
struct Data {
int a, b, d, suf_sum, suf_diff, pre_sum, pre_diff;
friend Data operator+(const Data& l, const Data& r)
{
int t = min(l.b, r.a);
Data x = (Data){l.a + r.a - t,
l.b + r.b - t,
check_inf(max(max(l.d, r.d), max(l.suf_sum + r.pre_diff, l.suf_diff + r.pre_sum))),
check_inf(max(r.suf_sum, max(l.suf_sum + r.b - r.a, l.suf_diff + r.b + r.a))),
check_inf(max(r.suf_diff, l.suf_diff + r.a - r.b)),
check_inf(max(l.pre_sum, max(l.a + l.b + r.pre_diff, l.a - l.b + r.pre_sum))),
check_inf(max(l.pre_diff, l.b - l.a + r.pre_diff))};
return x;
}
} x[N*3];
struct Segment_Tree {
Data v[N*12];
void build(int o, int l, int r)
{
if (l == r) {
v[o] = x[l];
return;
}
int m = (l+r)/2;
build(o*2, l, m);
build(o*2+1, m+1, r);
v[o] = v[o*2] + v[o*2+1];
}
void modify(int p, const Data& x, int o, int l, int r)
{
if (l == r) {
v[o] = x;
return;
}
int m = (l+r)/2;
if (p <= m) modify(p, x, o*2, l, m);
else modify(p, x, o*2+1, m+1, r);
v[o] = v[o*2] + v[o*2+1];
}
int query()
{
return v[1].d;
}
} T;
int dfn, pos[N+1];
bool state[N+1];
vector<int> adj[N+1];
void dfs(int u, int p)
{
x[dfn++] = BRACKET(0, 1);
pos[u] = dfn;
x[dfn++] = BLACK;
rep (i, 0, adj[u].size()) {
int v = adj[u][i];
if (v != p)
dfs(v, u);
}
x[dfn++] = BRACKET(1, 0);
}
int main()
{
int n;
scanf("%d", &n);
int num = n;
rep (i, 0, n-1) {
int u, v;
scanf("%d%d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1, 0);
T.build(1, 0, dfn-1);
int q;
scanf("%d", &q);
while (q--) {
char op;
int x;
scanf(" %c", &op);
if (op == 'G')
printf("%d\n", num ? (num == 1 ? 0 : T.query()) : -1);
else {
scanf("%d", &x);
T.modify(pos[x], state[x] ? BLACK : WHITE, 1, 0, dfn-1);
num += state[x] ? 1 : -1;
state[x] ^= 1;
}
}
return 0;
}