「SPOJ26374」QTREE5-LCT

你被给定一棵 $n$ 个点的树,点从 $1$ 到 $n$ 编号。每个点可能有两种颜色:黑或白。我们定义 $dist(a,b)$ 为点 $a$ 至点 $b$ 路径上的边个数。一开始所有的点都是黑色的。

要求作以下操作:

  • 0 i 将点 $i$ 的颜色反转(黑变白,白变黑)
  • 1 v 询问 $dist(u,v)$ 的最小值。$u$ 点必须为白色( $u$ 与 $v$ 可以相同),显然如果 $v$ 是白点,查询得到的值一定是 $0$ 。

特别地,如果作 1 操作时树上没有白点,输出 $-1$ 。

链接

Luogu

题解

我直接复制了 QTREE4 的代码…

主要改动如下:

  1. 把所有的 $\max$ 改成了 $\min$
  2. 把所有的边权改成 $1$
  3. 去除所有跟路径有关的东西

然后就ok了…

时间复杂度: $O(n \log^2 n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int MAXN = 210000;

struct Edge{
int to,nex;
}edge[MAXN*2];
int fir[MAXN],ecnt = 2;
void addedge(int a,int b){
edge[ecnt] = (Edge){b,fir[a]};
fir[a] = ecnt++;
}

inline int _f(multiset<int> &S){return S.size()?*S.begin():inf;}

struct LCT{
int c[MAXN][2],w[MAXN],f[MAXN],sum[MAXN];
int lmin[MAXN],rmin[MAXN];
multiset<int> Ch[MAXN];
void init(int n){for(int i = 0;i<=n;i++) w[i] = lmin[i] = rmin[i] = inf;}
bool noroot(int x){return c[f[x]][0] == x || c[f[x]][1] == x;}
void push_up(int x){assert(x);
#define ls c[x][0]
#define rs c[x][1]
sum[x] = sum[ls] + sum[rs] + 1;
int minc = min(w[x],_f(Ch[x]));
int L = min(minc,rmin[ls] + 1),R=min(minc,lmin[rs]);
lmin[x] = min(lmin[ls],R + sum[ls] + 1);
rmin[x] = min(rmin[rs],L + sum[rs]);
#undef ls
#undef rs
}
void rotate(int x){
int y = f[x],z = f[y],t = c[y][1] == x,w = c[x][1-t];
if(noroot(y)) c[z][c[z][1]==y] = x;
c[x][1-t] = y,c[y][t] = w;
if(w) f[w] = y;
f[y] = x,f[x] = z;
push_up(y);
}
void splay(int x){
while(noroot(x)){
int y = f[x],z = f[y];
if(noroot(y)){
(c[y][1]==x)^(c[z][1]==y)?rotate(x):rotate(y);
}rotate(x);
}push_up(x);
}
void access(int x){
for(int y = 0;x;x = f[y=x]){
splay(x);
if(c[x][1]) Ch[x].insert(lmin[c[x][1]]);
if(y) Ch[x].erase(Ch[x].find(lmin[y]));
c[x][1] = y,push_up(x);
}
}
void modify(int x){
access(x),splay(x);
w[x] = w[x]==0?inf:0;
push_up(x);
}
int query(int x){
access(x),splay(x);
return rmin[x];
}
void add(int x,int v){Ch[x].insert(lmin[v]);}
}T;


void dfs1(int x,int fa){
for(int nowe = fir[x];nowe;nowe = edge[nowe].nex){
int v = edge[nowe].to;
if(v == fa) continue;
T.f[v] = x,dfs1(v,x);
T.add(x,v);
}
T.push_up(x);
}

int n,q;

void init(){
scanf("%d",&n);
for(int i = 2;i<=n;i++){
int a,b;
scanf("%d %d",&a,&b);
addedge(a,b),addedge(b,a);
}
T.init(n);dfs1(1,0);
}

void solve(){
scanf("%d",&q);
int op, x;
for(int i = 1;i<=q;i++){
scanf("%d %d",&op,&x);
if(op == 1){
int ans = T.query(x);
if(ans < inf) printf("%d\n",ans);
else printf("-1\n");
}else if(op == 0) T.modify(x);
}
}

int main(){
init();
solve();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×