题目描述
给出一棵(N)个有色(黑白，黑色对应关灯，白色对应开灯)节点的树以及(M)次操作，每次操作将改变一个节点的颜色或者求出树上最远的两个白点距离
基本思路
(60pts)做法
这道题是动态点分治的板子题，动态点分治还是比(shi)较(fen)难写的。。。
所以我们先打一打部分分，瞄一眼数据范围：
对于(\%60)的数据，(Nleq3000,Mleq10000)
这样的数据很好做吧，我们用树的直径来搞就好了(还可以加一点卡常)。
求树的直径我用的是两次(DFS)，不过我们要改一点细节：
int id, __max, co[MAXN];
//co维护单点颜色，0表示黑色，1表示白色
inline void dfs(int u, int fa, int dis) {
if (dis >= __max && !co[u]) __max = dis, id = u;
//只有当点u为黑点才可以更新
for (rg int v, i = head[u]; i; i = nxt[i])
if ((v = ver[i]) ^ fa) dfs(v, u, dis + 1);
}
这样就改好了，复杂度还是(O(N))的。
在主函数里面，我们加一点这样的卡常：
因为这样的算法在执行修改时，只需(O(1))修改(co)数组，而更新答案是(O(N))的
所以我们只在每次查询时重新跑一遍(DFS)并且我们用一个变量(flag)，表示我们是否求出了最新的结果，这样就算有连续多次查询我们也可以马上输出答案走人。
(60pts)参考代码
/*--------------------------------
Code name: HideAndSeek.cpp
Author: The Ace Bee
This code is made by The Ace Bee
--------------------------------*/
#include <queue>
#include <cstdio>
#include <algorithm>
#define rg register
using namespace std;
const int MAXN = 100010;
inline int read() {
int s = 0; bool f = false; char c = getchar();
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return f ? -s : s;
}
int n, m;
int tot, head[MAXN], nxt[MAXN << 1], ver[MAXN << 1];
inline void Add_edge(int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }
int id, __max, co[MAXN];
inline void dfs(int u, int fa, int dis) {
if (dis >= __max && !co[u]) __max = dis, id = u;
for (rg int v, i = head[u]; i; i = nxt[i])
if ((v = ver[i]) ^ fa) dfs(v, u, dis + 1);
}
int main() {
n = read();
for (rg int u, v, i = 1; i <= n - 1; ++i)
u = read(), v = read(), Add_edge(u, v), Add_edge(v, u);
m = read(); char s[5]; bool flag = false;
for (rg int i = 1; i <= m; ++i) {
scanf("%s", s);
if (s[0] == 'C')
co[read()] ^= 1, flag = false;
else {
if (flag) printf("%d
", __max);
else {
__max = 0, dfs(1, 0, 0);
__max = 0, dfs(id, 0, 0);
printf("%d
", __max);
flag = true;
}
}
}
return 0;
}
(100pts)正解
上面也提到了，动态点分治难得写，所以我们还是打一发括号序列吧。
至于具体实现的话以及代码讲解的话，听说大家都是在一个地方，所以就不多赘述了(Orz 岛娘！！！)
那我可就直接上代码了(压行毒瘤qwq)
/*--------------------------------
Code name: HideAndSeek.cpp
Author: The Ace Bee
This code is made by The Ace Bee
--------------------------------*/
#include <cstdio>
#define rg register
const int INF = 2e9;
const int MAXN = 500010;
inline int max(int a, int b) { return a > b ? a : b ; }
inline int read() {
int s = 0; bool f = false; char c = getchar();
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return f ? -s : s;
}
int tot, head[MAXN], nxt[MAXN << 1], ver[MAXN << 1];
inline void Add_edge(int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }
int n, m, col[MAXN];
int black, len, s[MAXN * 3], pos[MAXN];
inline void dfs(int u, int fa) {
s[++len] = -1;
s[++len] = u, pos[u] = len;
for (rg int v, i = head[u]; i; i = nxt[i])
if ((v = ver[i]) ^ fa) dfs(v, u);
s[++len] = -2;
}
struct node{ int a, b, l1, l2, r1, r2, dis; }c[MAXN << 2];
inline int lc(int rt) { return rt << 1; }
inline int rc(int rt) { return rt << 1 | 1; }
inline void upt(int rt, int x) {
c[rt].a = c[rt].b = 0;
c[rt].l1 = c[rt].l2 = c[rt].r1 = c[rt].r2 = c[rt].dis = -1e9;
if (s[x] == -1) { c[rt].b = 1; return ; }
if (s[x] == -2) { c[rt].a = 1; return ; }
if (!col[s[x]]) c[rt].l1 = c[rt].l2 = c[rt].r1 = c[rt].r2 = c[rt].dis = 0;
}
inline void pushup(int rt) {
if (c[lc(rt)].b > c[rc(rt)].a)
c[rt].a = c[lc(rt)].a, c[rt].b = c[lc(rt)].b - c[rc(rt)].a + c[rc(rt)].b;
else
c[rt].a = c[lc(rt)].a - c[lc(rt)].b + c[rc(rt)].a, c[rt].b = c[rc(rt)].b;
c[rt].l1 = max(c[lc(rt)].l1, max(c[rc(rt)].l1 + c[lc(rt)].a - c[lc(rt)].b, c[rc(rt)].l2 + c[lc(rt)].a + c[lc(rt)].b));
c[rt].l2 = max(c[lc(rt)].l2, c[rc(rt)].l2 - c[lc(rt)].a + c[lc(rt)].b);
c[rt].r1 = max(c[rc(rt)].r1, max(c[lc(rt)].r1 - c[rc(rt)].a + c[rc(rt)].b, c[lc(rt)].r2 + c[rc(rt)].a + c[rc(rt)].b));
c[rt].r2 = max(c[rc(rt)].r2, c[lc(rt)].r2 + c[rc(rt)].a - c[rc(rt)].b);
c[rt].dis = max(max(c[lc(rt)].dis, c[rc(rt)].dis), max(c[lc(rt)].r1 + c[rc(rt)].l2, c[lc(rt)].r2 + c[rc(rt)].l1));
}
inline void build(int rt, int l, int r) {
if (l == r) { upt(rt, l); return ; }
int mid = (l + r) >> 1;
build(lc(rt), l, mid), build(rc(rt), mid + 1, r);
pushup(rt);
}
inline void update(int rt, int l, int r, int id) {
if (l == r) { upt(rt, l); return; }
int mid = (l + r) >> 1;
if (id <= mid) update(lc(rt), l, mid, id);
else update(rc(rt), mid + 1, r, id);
pushup(rt);
}
int main() {
black = n = read();
for (rg int u, v, i = 1; i <= n - 1; ++i)
u = read(), v = read(), Add_edge(u, v), Add_edge(v, u);
dfs(1, 0);
build(1, 1, len);
m = read();
char ss[5];
for (rg int i = 1; i <= m; ++i) {
scanf("%s", ss);
if (ss[0] == 'C') {
int x = read();
black += col[x] ? -1 : 1;
col[x] ^= 1, update(1, 1, len, pos[x]);
} else {
if (black == 0) puts("-1");
else if (black == 1) puts("0");
else printf("%d
", c[1].dis);
}
}
return 0;
}
完结撒花(qwq)