https://www.luogu.com.cn/problem/CF403E
I want to delete all the outward edges of a certain subtree of a tree.
In dfn order, one is in the subtree interval and the other is not.
It is easy to find that this problem can be maintained using line segment trees.
Add another point at a point in its dfn order, and maintain the maximum and minimum values of the dfn order of another point in the interval.
If it is not in the query range, recurse directly
It is easy to prove that equal apportionment is
O
(
n
log
?
n
)
O(n\log n)
O(nlogn)
For such problems of even amortization of operations, you can consider using line segment tree maintenance.
//5.1k
#include<bits/stdc + + .h>
using namespace std;
//#define int long long
inline int read(){<!-- -->int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){<!-- -->if(ch=='-')f=-1;ch=getchar();}while(ch>='0' & amp; & amp;ch <='9'){<!-- -->
x=(x<<1) + (x<<3) + (ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 200010
//#define M
//#define mo
#define first
#define se second
int n, m, i, j, k, idx;
//map<pair<int, int>, int>mp[2];
// unordered_map<pair<int, int>, int>mp;
int mp[2][N];
queue<pair<int, int> >q[2];
struct Segment_tree {<!-- -->
int o;
int tot, ls[N<<2], rs[N<<2];
int dfn[N<<2], low[N<<2];
int mn[N<<2], mx[N<<2];
struct node {<!-- -->
int x, id;
};
vector<node>v[N<<2];
int ST[N<<2], ED[N<<2];
void build(int & amp;k, int l, int r) {<!-- -->
if(!k) k= + + tot, mn[k]=l, mx[k]=r;
if(l==r) return;
int mid=(l + r)>>1;
build(ls[k], l, mid);
build(rs[k], mid + 1, r);
}
void add(int k, int l, int r, int x, int y, int z) {<!-- -->//order x point y
if(l==r) return v[k].pb({<!-- -->y, z}), void();
int mid=(l + r)>>1;
if(x<=mid) add(ls[k], l, mid, x, y, z);
else add(rs[k], mid + 1, r, x, y, z);
}
void push_up(int k) {<!-- -->
mn[k]=min(mn[ls[k]], mn[rs[k]]);
mx[k]=max(mx[ls[k]], mx[rs[k]]);
}
void remke(int k, int l, int r) {<!-- -->
if(l==r) {<!-- -->
int & amp;st = ST[k], & amp;ed = ED[k];
sort(v[k].begin(), v[k].end(), [this] (node x, node y)
{<!-- -->return dfn[x.x]<dfn[y.x]; } ); //Save points in v
st=0; ed=v[k].size()-1;
if(ed>=0) mn[k]=dfn[v[k][st].x], mx[k]=dfn[v[k][ed].x];
// printf("# %d [%d -> %d] %d %d\
", o, l, low[l], mn[k], mx[k]);
return ;
}
int mid=(l + r)>>1;
remke(ls[k], l, mid);
remke(rs[k], mid + 1, r);
push_up(k);
}
void tak(int k, int l, int r, int x, int y) {<!-- -->
// printf("%d [%d ]")
if(l>=x & amp; & amp; r<=y) {<!-- -->
if(l==r) {<!-- -->
if(!v[k].size()) return mn[k]=mx[k]=l, void();
int & amp;st = ST[k], & amp;ed = ED[k];
while(st<=ed & amp; & amp; dfn[v[k][st].x]<x) {<!-- -->
int u = v[k][st].x, id = v[k][st].id, v = low[l];
if(!mp[o^1][id]) {<!-- -->
// printf("# %d : (%d %d) | %d\
", o^1, u, v, id);
// mp[o^1][{u, v}]=mp[o^1][{v, u}]=1;
mp[o^1][id]=1;
q[o^1].push({<!-- -->u, v});
}
+ + st;
}
while(st<=ed & amp; & amp; dfn[v[k][ed].x]>y) {<!-- -->
int u = v[k][ed].x, id = v[k][ed].id, v = low[l];
if(!mp[o^1][id]) {<!-- -->
// printf("# %d : (%d %d) | %d\
", o^1, u, v, id);
mp[o^1][id]=1;
q[o^1].push({<!-- -->u, v});
}
--ed;
}
if(st<=ed) mn[k]=dfn[v[k][st].x], mx[k]=dfn[v[k][ed].x];
else mn[k]=mx[k]=l;
return;
}
int mid=(l + r)>>1;
if(mn[ls[k]]<x || mx[ls[k]]>y) tak(ls[k], l, mid, x, y);
if(mn[rs[k]]<x || mx[rs[k]]>y) tak(rs[k], mid + 1, r, x, y);
push_up(k);
return ;
}
int mid=(l + r)>>1;
if(x<=mid) tak(ls[k], l, mid, x, y);
if(y>=mid + 1) tak(rs[k], mid + 1, r, x, y);
push_up(k);
}
}Seg[2]; //Which tree the dfn sequence is, this corresponds to which tree
struct Tree {<!-- -->
int o;
int dfn[N], low[N], st[N], ed[N];
int i, j, k, tot, rt;
vector<pair<int, int> >G[N];
vector<pair<int, int> >ve;
map<pair<int, int>, int>id;
\t
void dfs(int x, int fa) {<!-- -->
dfn[x]= + + tot; st[x]=tot; low[tot]=x;
for(auto t : G[x]) if(t.first!=fa)
dfs(t.first, x);
ed[x]= tot;
}
void Read() {<!-- -->
for(i=2; i<=n; + + i) {<!-- -->
k=read(); G[i].pb({<!-- -->k, i-1});
G[k].pb({<!-- -->i, i-1});
ve.pb({<!-- -->i, k});
id[{<!-- -->i, k}]=id[{<!-- -->k, i}]=i-1;
}
Seg[o].build(rt, 1, n);
dfs(1, 0);
// for(i=1; i<=n; + + i) printf("%d ", dfn[i]); puts("");
}
void pre();
void tak(int u, int v) {<!-- --> // Take away one of the points [l, r]
// printf("[%d %d]\
", max(st[u], st[v]), min(ed[u], ed[v]));
Seg[o].tak(1, 1, n, max(st[u], st[v]), min(ed[u], ed[v]));
}
};
Tree T[2];
void Tree::pre() {<!-- -->
// printf("# %d\
", o);
for(auto t : ve) {<!-- -->
int x=t.fi, y=t.se;
int u=T[o^1].dfn[x], v=T[o^1].dfn[y];
// printf("(%d %d) [%d %d] %d\
", x, y, u, v, x-1);
Seg[o^1].add(1, 1, n, u, y, x-1);
Seg[o^1].add(1, 1, n, v, x, x-1);
}
Seg[o^1].remke(1, 1, n);
}
signed main()
{<!-- -->
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// T=read();
// while(T--) {<!-- -->
//
// }
n=read();
T[0].o=0; T[1].o=1;
Seg[0].o=0; Seg[1].o=1;
T[0].Read(); T[1].Read();
memcpy(Seg[0].dfn, T[0].dfn, sizeof(T[0].dfn));
memcpy(Seg[0].low, T[0].low, sizeof(T[0].low));
memcpy(Seg[1].dfn, T[1].dfn, sizeof(T[1].dfn));
memcpy(Seg[1].low, T[1].low, sizeof(T[1].low));
T[0].pre(); T[1].pre();
idx=read();
for(auto t : T[0].id)
if(t.se==idx & amp; & amp; !mp[0][idx]) {<!-- -->
int u = t.fi.fi, v = t.fi.se;
q[0].push({<!-- -->u, v});
mp[0][idx]=1;
// printf("(%d %d) %d\
", u, v, );
}
\t\t
k=0;
vector<int>ans;
while(!q[k].empty()) {<!-- -->
printf(k? "Red\
" : "Blue\
");
ans.clear();
while(!q[k].empty()) {<!-- -->//The dot is placed in q
auto t = q[k].front(); q[k].pop();
ans.pb(T[k].id[{<!-- -->t.fi, t.se}]);
T[k].tak(t.fi, t.se);
}
sort(ans.begin(), ans.end());
for(auto i : ans) printf("%d ", i);
puts("");
k^=1;
}
return 0;
}