C. Max Mex
https://codeforces.com/contest/1083/problem/C
题意：
一棵$n$个点的树，每个点上有一个数（每个点的上的数互不相同，而且构成一个0~n-1的排列），要求找到一条路径，使得路径的$mex$最大。
分析：
问题转化为，查询一个a，0~a-1是否可以都存在于一条路径上。类似线段树维护连通性，这里线段树的每个点表示所对应的区间[l,r]是否可以存在于一条路径上。合并的时候用lca和dfs序的位置判断。然后就是线段树上二分了。
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#define Root 0, n - 1, 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
const int Log = ; struct Edge{
int to, nxt;
Edge() {}
Edge(int a,int b) { to = a, nxt = b; }
}e[N];
int head[N], a[N], per[N], In[N], Ou[N], deth[N], f[N][Log + ], En, Index;
struct Node{
int x, y;
Node() {}
Node(int _x,int _y) { x = _x, y = _y; }
}T[N << ];
bool operator < (const Node &A,const Node &B) {
return A.x == B.x ? A.y < B.y : A.x < B.x;
}
int Jump(int x,int ly) {
for (int i = Log; i >= ; --i)
if (deth[f[x][i]] >= ly) x = f[x][i]; // 这里要求deth[1]=1
return x;
}
int LCA(int u,int v) {
if (deth[u] < deth[v]) swap(u, v);
int d = deth[u] - deth[v];
for (int i = Log; i >= ; --i)
if ((d >> i) & ) u = f[u][i];
if (u == v) return u;
for (int i = Log; i >= ; --i)
if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][];
}
bool onpath(int x,int y,int z) {
int anc = LCA(x, y);
if (deth[anc] > deth[z]) return ;
return Jump(x, deth[z]) == z || Jump(y, deth[z]) == z;
}
Node operator + (const Node &A,const Node &B) {
int a = A.x, b = A.y, c = B.x, d = B.y;
if (a == - || b == - || c == - || d == -) return Node(-, -);
int x = min(Node(Ou[a], a), min(Node(Ou[b], b), min(Node(Ou[c], c), Node(Ou[d], d)))).y; //dfs序上较小的路位置
int y = max(Node(In[a], a), max(Node(In[b], b), max(Node(In[c], c), Node(In[d], d)))).y; //dfs序上较大的路位置
if (x == y) { // 在同一条链上的情况
int z = min(Node(deth[a], a), min(Node(deth[b], b), min(Node(deth[c], c), Node(deth[d], d)))).y;
return Node(z, x);
}
else if (onpath(x, y, a) && onpath(x, y, b) && onpath(x, y, c) && onpath(x, y, d)) return Node(x, y);
else return Node(-, -);
}
inline void add_edge(int u,int v) {
++En; e[En] = Edge(v, head[u]); head[u] = En;
}
void dfs(int u) {
In[u] = ++Index;
for (int i = head[u]; i; i = e[i].nxt) deth[e[i].to] = deth[u] + , dfs(e[i].to);
Ou[u] = ++Index;
}
void build(int l,int r,int rt) {
if (l == r) {
T[rt].x = T[rt].y = per[l]; return ;
}
int mid = (l + r) >> ;
build(lson); build(rson);
T[rt] = T[rt << ] + T[rt << | ];
}
void update(int l,int r,int rt,int p,int v) {
if (l == r) {
T[rt].x = T[rt].y = v; return ;
}
int mid = (l + r) >> ;
if (p <= mid) update(lson, p, v);
if (p > mid) update(rson, p, v);
T[rt] = T[rt << ] + T[rt << | ];
}
int query(int l,int r,int rt,Node now) {
if (l == r) {
return (now + T[rt]).x == - ? l - : l;
}
int mid = (l + r) >> ;
Node tmp = now + T[rt << ];
if (tmp.x == -) return query(lson, now);
else return query(rson, tmp);
}
int main() {
int n = read();
for (int i = ; i <= n; ++i) a[i] = read(), per[a[i]] = i; // a[i]第i个节点的数，per[i]数字为i的在树的那个节点上
for (int i = ; i <= n; ++i) {
int fa = read();
add_edge(fa, i);
f[i][] = fa;
}
for (int j = ; j <= Log; ++j)
for (int i = ; i <= n; ++i)
f[i][j] = f[f[i][j - ]][j - ];
deth[] = ; dfs();
build(Root);
int Q = read();
while (Q--) {
int opt = read();
if (opt == ) {
printf("%d\n", query(Root, Node(per[], per[])) + );
continue;
}
int x = read(), y = read();
swap(per[a[x]], per[a[y]]);
update(Root, a[x], per[a[x]]);
update(Root, a[y], per[a[y]]);
swap(a[x], a[y]);
}
return ;
}