题目
题目描述
狉狉牛家里有一个很大的养鱼场，所以他天天摸鱼！他常常试图否认这一事实。
今天他要给他的朋友 s y \tt sy sy 送一些鱼。可是鱼是在游动的，有的时候鱼浮出水面吐泡泡，你就可以一把抓住——前提是你在这个码头；如果鱼潜入深处，你就拿它毫无办法。
狉狉牛的所有 n n n 个码头，和连接它们的 n − 1 n-1 n−1 条路，恰好形成了一个树形结构。由于 1 1 1 号码头是狉狉牛最初的码头——也就是他的摸鱼事业开始的地方——它会是树的根，不过那里的条件是最糟的。以此类推，距离 1 1 1 号码头越近，条件就越差。
s y \tt sy sy 站在某个地方时，他得通过路径移动到某个有鱼浮起的码头，然后拿一条。这条路径他可以任意选——他走不走回头路是自己的事，但是有些码头是所有路径都会经过的。这种必要的码头中条件最差的一个就是 “限制码头” 。 s y \tt sy sy 希望选择一个码头，使得 “限制码头” 的条件最好。你只要告诉她最好的 “限制码头” 是哪一个就行了！
不过鱼是在游动的， s y \tt sy sy 也会很多次地向你请教。你能帮忙吗？
最开始所有的码头都看不到鱼，唯见长江天际流。
数据范围与提示
max
(
n
,
q
)
≤
8
×
1
0
5
\max(n,q)\le 8\times 10^5
max(n,q)≤8×105 。
思路壹
转化题意：操作为翻转一个点的颜色，与询问所有黑色点与当前点的 l c a \tt lca lca 中深度最大的一个。
显然直接树剖，将一个黑色点到根的路径全部标记为黑色，然后询问当前点到根上的标记点中最深的一个。
O
(
n
log
2
n
)
\mathcal O(n\log^2n)
O(nlog2n) 好像不能接受？那就写
O
(
n
log
n
)
\mathcal O(n\log n)
O(nlogn) 吧！虽然实际上可能不会快很多。
代码壹
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
inline int readint(){
int a = 0; char c = getchar(), f = 1;
for(; c<'0'||c>'9'; c=getchar())
if(c == '-') f = -f;
for(; '0'<=c&&c<='9'; c=getchar())
a = (a<<3)+(a<<1)+(c^48);
return a*f;
}
inline void getMax(int &a,const int &b){
(a < b) ? (a = b) : 0;
}
const int MaxN = 800005;
struct Edge{
int to, nxt;
};
Edge e[MaxN];
int head[MaxN], cntEdge;
void addEdge(int a,int b){
e[cntEdge].to = b;
e[cntEdge].nxt = head[a];
head[a] = cntEdge ++;
}
int siz[MaxN], son[MaxN];
int lsiz[MaxN]; // size of light son
void getInfo(int x){
siz[x] = 1, son[x] = 0;
for(int i=head[x]; ~i; i=e[i].nxt){
getInfo(e[i].to);
siz[x] += siz[e[i].to];
if(siz[e[i].to] > siz[son[x]])
son[x] = e[i].to;
}
lsiz[x] = siz[x]-siz[son[x]];
}
int fa[MaxN], zi[MaxN][2];
int col[MaxN]; // 自己、轻儿子中黑点个数
int all[MaxN], ys[MaxN], tot;
bool isRt[MaxN]; // 父边为虚边么
int mx[MaxN]; // 深度最大的黑点
void pushUp(int x){
if(col[x] > 0) // 自己是黑点
mx[x] = x; // maybe myself
else mx[x] = 0; // init
if(mx[zi[x][1]] != 0)
mx[x] = mx[zi[x][1]];
else if(mx[x] == 0)
mx[x] = mx[zi[x][0]];
}
int build(int l,int r){
if(l > r) return 0;
int x = lower_bound(all+l,all+r+1,
(all[l-1]+all[r])>>1)-all;
zi[ys[x]][0] = build(l,x-1);
zi[ys[x]][1] = build(x+1,r);
x = ys[x]; // 实际的点
return fa[zi[x][0]] =
fa[zi[x][1]] = x;
}
int dfs(int x){
ys[++ tot] = x; // 映射
all[tot] += lsiz[x];
if(head[x] == -1){
int rt = build(1,tot);
tot = all[1] = 0;
return rt; // 记得清空
}
all[tot+1] = all[tot];
int rt = dfs(son[x]);
for(int i=head[x]; ~i; i=e[i].nxt)
if(e[i].to != son[x]){
int sy = dfs(e[i].to);
fa[sy] = x, isRt[sy] = 1;
}
return rt;
}
void updata(int x,int v){
col[x] += v; // itself
while(fa[x] != 0){
if(isRt[x]) col[fa[x]] += v;
pushUp(x); x = fa[x];
}
pushUp(x); // 少了一次
}
int queryChain(int x){
if(col[x] > 0 || mx[zi[x][1]])
return x; // 自己是黑的
int ans = mx[zi[x][0]];
for(int i=x; !isRt[i]; i=fa[i])
if(i == zi[fa[i]][0]){
if(col[fa[i]] > 0
|| mx[zi[fa[i]][1]])
return x;
}
else if(!ans && col[fa[i]] > 0)
ans = fa[i]; // 深度尽量大
else if(!ans) // 前面得到的必然更深
ans = mx[zi[fa[i]][0]];
return ans;
}
int query(int x){
int ans = queryChain(x);
for(; fa[x]&&!ans; x=fa[x])
if(isRt[x]) // 跳到新的链上
ans = queryChain(fa[x]);
return ans;
}
bool tag[MaxN];
int main(){
int n = readint(), q = readint();
for(int i=1; i<=n; ++i)
head[i] = -1;
for(int i=2; i<=n; ++i)
addEdge(readint(),i);
getInfo(1), isRt[dfs(1)] = 1;
while(q --){
int x = readint();
if(x < 0)
printf("%d\n",query(-x));
else{
updata(x,tag[x]?-1:1);
tag[x] = !tag[x];
}
}
return 0;
}
思路贰
l c a lca lca 深度最小的一定是 d f s \tt dfs dfs 序最靠近的。所以只需要求两次 l c a lca lca 即可。
复杂度 O ( n log n ) \mathcal O(n\log n) O(nlogn) ，结果倍增求 l c a lca lca 还会被卡常