你被给定一棵n个点的树,点从1到n编号。每个点可能有两种颜色:黑或白。我们定义dist(a,b)为点a至点b路径上的边个数。
一开始所有的点都是黑色的。
要求作以下操作:
0 i 将点i的颜色反转(黑变白,白变黑)
1 v 询问dist(u,v)的最小值。u点必须为白色(u与v可以相同),显然如果v是白点,查询得到的值一定是0。
特别地,如果作'1'操作时树上没有白点,输出-1。
动态点分治解决该问题
LCT解法
我们知道LCT实际上是多个Splay的森林,它有实虚边之分,实边的贡献是很好记录的,而虚边需要我们在用堆或者一些数据结构来进行维护。
参考了网上的一些思维的方式,我假设这棵树的实际的根为“1”,也就是我假定原树的根是“1”,那么对于其余的点,我们将边的权值赋值到点上去,也就是dfs之后,是,那么就给v点权值为“1”,因为本题是单位边权。
假设不改变树的实际根,也就是我们不会让makeroot()这个函数出现,保证了整棵树的深度,就是LCT中Spay的子树的“左中右”的遍历顺序。
那我维护这样的两个东西:
:表示在Splay图中,以x为子树的根的时候的最浅的结点所能到达的白点的最近距离。
:表示在Splay图中,以x为子树的根的时候的最深的结点所能到达的白点的最近距离。
于是,我们可以试着列写pushup方程。
- 可以是通过左儿子(深度比他浅的结点)直接继承它的,也就是;
- 也有可能是自己本身,如果要算上自己的话,说明要经过从原图中x的父亲到x的这条边了,所以要把x结点的权值加上来;
- 是从深度最浅的点,去找到它(x)的右子树上的点所能到达的最近的白点,那么应该去找rc(右子结点)为根的Splay子树上最浅的点所能到达的最近白点,距离和就是,size[lc]是x的最浅点到x的距离,val[x]是因为要从x的父亲走到x了,所以会加上x的距离,通过size[lc] + val[x]就可以保证最浅的结点能到达x点了,lmn[rc]是rc的Splay子树中最浅的点能到达的最近白点,因为它们是一条链上的,所以就不需要担心。
- 另外,不要忘记对虚边的处理,我们可以用一个堆将所有的lmn[x]存起来,然后与“3操作”类似,变成了即可。
关于的补充部分,我在这里算的,实际上有的lmn[x]是多算了,因为有的点是算上了它到原树中父亲的距离,所以在做比较的时候,要分析清晰。
- 首先,肯定是要看能不能继承原来rs的值,也就是;
- 依然有可能是到自己本身的,那么此时由于是从深度更深的点过来的,所以就不用加val[x]了,变成了;
- 要是遇到要经过x点去lc查找的时候呢,就会经过x,去往另一个方向了,此时距离x最近的点就是rmn[ls]对应的点了,因为x与x最接近的肯定就是深度深的,左子树中深度最深的就是了,于是就是。
- 最后,不要忘记的是虚边,与x相连的虚边,那么就是去找堆中的最小值,因为是不经过val[x]的边的,所以这里不要加v al[x],是。
最后,我们要查询的对吧,查询怎么查?将要查询的点作为深度最深的结点,也就是将它access到根之后,Splay到root,那么它的rmn[x]就是我们要查询的答案了,因为rmn[x]维护的是Splay子树中最深的点到最近白点的距离。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
//#include <unordered_map>
//#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
//const int maxN = 11;
int N, Q, white, c[maxN][2], r[maxN], fa[maxN], size[maxN], col[maxN], lmn[maxN], rmn[maxN], w[maxN], val[maxN];
struct heap
{
priority_queue<int, vector<int> , greater<int> > Que, Del;
inline bool empty()
{
while(!Que.empty() && !Del.empty() && Que.top() == Del.top()) { Que.pop(); Del.pop(); }
return Que.empty();
}
inline void push(int val) { Que.push(val); }
inline void clear(int val) { Del.push(val); }
inline int size() { return (int)(Que.size() - Del.size()); }
inline int top()
{
while(!Que.empty() && !Del.empty() && Que.top() == Del.top()) { Que.pop(); Del.pop(); }
return !Que.empty() ? Que.top() : INF;
}
inline void pop()
{
while(!Que.empty() && !Del.empty() && Que.top() == Del.top()) { Que.pop(); Del.pop(); }
Que.pop();
}
} s[maxN];
inline bool isroot(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; }
inline void pushup(int x)
{
if(!x) return;
size[x] = size[c[x][0]] + size[c[x][1]] + val[x];
lmn[x] = min(lmn[c[x][0]], size[c[x][0]] + min(w[x], min(s[x].top(), lmn[c[x][1]])) + val[x]);
rmn[x] = min(rmn[c[x][1]], size[c[x][1]] + min(w[x], min(s[x].top(), rmn[c[x][0]] + val[x])));
}
inline void pushr(int x)
{
if(!x) return;
swap(c[x][0], c[x][1]);
r[x] ^= 1;
}
inline void pushdown(int x)
{
if(!x) return;
if(r[x])
{
pushr(c[x][0]);
pushr(c[x][1]);
r[x] = 0;
}
}
void Rotate(int x)
{
int y = fa[x], z = fa[y], k = c[y][1] == x, cop = c[x][k ^ 1];
if(!isroot(y)) c[z][c[z][1] == y] = x;
fa[x] = z;
c[y][k] = cop;
fa[cop] = y;
c[x][k ^ 1] = y;
fa[y] = x;
pushup(y); pushup(x);
}
int Stap[maxN];
void Splay(int x)
{
int y = x, z = 0;
Stap[++z] = y;
while(!isroot(y)) Stap[++z] = y = fa[y];
while(z) pushdown(Stap[z--]);
while(!isroot(x))
{
y = fa[x]; z = fa[y];
if(!isroot(y)) (c[z][0] == y) ^ (c[y][0] == x) ? Rotate(x) : Rotate(y);
Rotate(x);
}
}
void access(int x)
{
int y = 0;
while(x)
{
Splay(x);
if(c[x][1]) s[x].push(lmn[c[x][1]]);
if(y) s[x].clear(lmn[y]);
c[x][1] = y;
pushup(x);
y = x; x = fa[x];
}
}
int head[maxN], cnt;
struct Eddge
{
int nex, to;
Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
inline void addEddge(int u, int v)
{
edge[cnt] = Eddge(head[u], v);
head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
void dfs(int u, int father)
{
for(int i=head[u], v; ~i; i=edge[i].nex)
{
v = edge[i].to;
if(v == father) continue;
fa[v] = u; val[v] = 1;
dfs(v, u);
s[u].push(lmn[v]);
}
pushup(u);
}
void update(int x)
{
access(x);
Splay(x);
col[x] ^= 1;
w[x] = col[x] ? 0 : INF;
if(col[x]) white++;
else white--;
pushup(x);
}
inline int query(int x)
{
access(x); Splay(x);
return rmn[x];
}
inline void init()
{
white = 0; lmn[0] = rmn[0] = INF;
for(int i=1; i<=N; i++)
{
r[i] = 0; c[i][0] = c[i][1] = 0; head[i] = -1; col[i] = 0;
size[i] = 1;
lmn[i] = rmn[i] = w[i] = INF;
}
}
int main()
{
scanf("%d", &N);
init();
for(int i=1, u, v; i<N; i++)
{
scanf("%d%d", &u, &v);
_add(u, v);
}
val[1] = 0;
dfs(1, 0);
scanf("%d", &Q);
int op, x;
while(Q--)
{
scanf("%d%d", &op, &x);
if(!op)
{
update(x);
}
else
{
if(!white) printf("-1\n");
else printf("%d\n", query(x));
}
}
return 0;
}