题解
写数据结构的时候我代码就会变得非常非常长
一看别人1.5K 2.3K
我6.3K……
orzzzzz
我们很容易想到离线倒着插入，然而，有个小锅叫如果size相同保持原来的重儿子不变
我们需要写个线段树，遇到两个size相同的儿子时看两个儿子下一次插入是什么时候，取下一次插入时间较大的儿子，如果都没有插入，取左儿子
最后类似lct一样用splay维护每条链，但是我们不用维护虚边，要支持给splay打标记，因为我们插入一个点要给整条链增加一遍size
代码
#include <bits/stdc++.h>
#define enter putchar('
')
#define space putchar(' ')
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define MAXN 200005
#define mo 99994711
#define pb push_back
#define eps 1e-8
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;T f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 - '0' + c;
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,Q;
int L[MAXN],R[MAXN],fa[MAXN],rt;
int D[MAXN],son[MAXN],siz[MAXN],dfn[MAXN],idx,Line[MAXN],tims[MAXN];
bool vis[MAXN];
int64 sum,ans[MAXN];
namespace seg_tr {
struct tr_node {
int l,r,v;
}tr[MAXN * 4];
void update(int u) {
tr[u].v = max(tr[u << 1].v,tr[u << 1 | 1].v);
}
void build(int u,int l,int r) {
tr[u].l = l;tr[u].r = r;
if(l == r) {tr[u].v = tims[Line[l]];return;}
int mid = (l + r) >> 1;
build(u << 1,l,mid);
build(u << 1 | 1,mid + 1,r);
update(u);
}
void Change(int u,int pos) {
if(tr[u].l == tr[u].r) {tr[u].v = 0;return;}
int mid = (tr[u].l + tr[u].r) >> 1;
if(pos <= mid) Change(u << 1,pos);
else Change(u << 1 | 1,pos);
update(u);
}
int Query(int u,int l,int r) {
if(l > r) return 0;
if(tr[u].l == l && tr[u].r == r) return tr[u].v;
int mid = (tr[u].l + tr[u].r) >> 1;
if(r <= mid) return Query(u << 1,l,r);
else if(l > mid) return Query(u << 1 | 1,l,r);
else return max(Query(u << 1,l,mid),Query(u << 1 | 1,mid + 1,r));
}
}
namespace splay {
struct node {
node *lc,*rc,*fa;
int siz,add;
void add_lazy(int v) {
add += v;
siz += v;
}
void push_down() {
if(lc) lc->add_lazy(add);
if(rc) rc->add_lazy(add);
add = 0;
}
}pool[MAXN],*tail = pool,*tr[MAXN];
node *que[MAXN];
int tot;
node *Newnode() {
node *res = tail++;
res->lc = res->rc = res->fa = NULL;
res->siz = 0;res->add = 0;
return res;
}
void Init(int N) {
for(int i = 1 ; i <= N ; ++i) tr[i] = Newnode();
}
void rotate(node *u) {
node *v = u->fa,*w = v->fa;
if(w) (v == w->lc ? w->lc : w->rc) = u;
node *b = (u == v->lc ? u->rc : u->lc);
if(b) b->fa = v;
v->fa = u;u->fa = w;
if(u == v->lc) {u->rc = v;v->lc = b;}
else {u->lc = v;v->rc = b;}
}
bool which(node *u) {
return u->fa->rc == u;
}
void Splay(node *u) {
tot = 0;
for(node *x = u ; x ; x = x->fa) que[++tot] = x;
for(int i = tot ; i >= 1 ; --i) que[i]->push_down();
while(u->fa) {
if(u->fa->fa) {
if(which(u) == which(u->fa)) rotate(u->fa);
else rotate(u);
}
rotate(u);
}
}
}
using seg_tr::Change;
using seg_tr::Query;
using splay::Splay;
using splay::pool;
using splay::tr;
void dfs1(int u) {
dfn[u] = ++idx;Line[idx] = u;
siz[u] = 1;
if(L[u]) {dfs1(L[u]);siz[u] += siz[L[u]];}
if(R[u]) {dfs1(R[u]);siz[u] += siz[R[u]];}
}
int dfs2(int u) {
if(vis[u] || !u) {return 0;}
int res = 1,s1,s2;
s1 = dfs2(L[u]);s2 = dfs2(R[u]);
res += s1 + s2;tr[u]->siz = res;
if(s1 == 0 && s2 == 0) return res;
if(!s1) son[u] = R[u];
else if(!s2) son[u] = L[u];
else {
if(s1 > s2) son[u] = L[u];
else if(s2 > s1) son[u] = R[u];
else {
s1 = Query(1,dfn[L[u]],dfn[L[u]] + siz[L[u]] - 1);
s2 = Query(1,dfn[R[u]],dfn[R[u]] + siz[R[u]] - 1);
if(s1 >= s2) son[u] = L[u];
else son[u] = R[u];
}
}
if(son[u]) {
Splay(tr[son[u]]);
tr[u]->rc = tr[son[u]];
tr[son[u]]->fa = tr[u];
}
return res;
}
bool check(int u,int v) {
int s1 = Query(1,dfn[u],dfn[u] + siz[u] - 1),s2 = Query(1,dfn[v],dfn[v] + siz[v] - 1);
if(s1 > s2 || (s1 == s2 && u == L[fa[u]])) return true;
return false;
}
void Insert(int u) {
while(u) {
int f = fa[u];
Splay(tr[u]);
if(!f) break;
bool flag = 0;
if(!son[f]) {flag = 1;}
else {
Splay(tr[son[f]]);
if(tr[son[f]]->siz < tr[u]->siz + 1) flag = 1;
else if(tr[son[f]]->siz == tr[u]->siz + 1) flag = check(u,son[f]);
}
if(flag) {
Splay(tr[f]);Splay(tr[u]);
if(tr[f]->rc) tr[f]->rc->fa = NULL;
tr[f]->rc = tr[u];tr[u]->fa = tr[f];
sum += u - son[f];son[f] = u;
}
Splay(tr[u]);
splay::node *p = tr[u];
while(p->lc) p = p->lc;
u = p - pool + 1;
if(!flag) {
u = fa[u];
Splay(tr[u]);
p = tr[u];
while(p->lc) p = p->lc;
u = p - pool + 1;
}
}
}
void Change_size(int u) {
while(u) {
Splay(tr[u]);
if(tr[u]->lc) tr[u]->lc->add_lazy(1);
tr[u]->siz++;
splay::node *p = tr[u];
while(p->lc) p = p->lc;
u = p - pool + 1;
u = fa[u];
}
}
void Solve() {
read(N);
for(int i = 1 ; i <= N ; ++i) {read(L[i]);read(R[i]);fa[L[i]] = i;fa[R[i]] = i;}
splay::Init(N);
for(int i = 1 ; i <= N ; ++i) {if(!fa[i]) rt = i;}
read(Q);
for(int i = 1 ; i <= Q ; ++i) {read(D[i]);vis[D[i]] = 1;tims[D[i]] = i;}
dfs1(rt);
seg_tr::build(1,1,N);
dfs2(rt);
sum = 0;
for(int i = 1 ; i <= N ; ++i) sum += son[i];
ans[Q + 1] = sum;
for(int i = Q ; i >= 1 ; --i) {
Change(1,dfn[D[i]]);
Insert(D[i]);
Change_size(D[i]);
ans[i] = sum;
}
for(int i = 1 ; i <= Q + 1; ++i) {out(ans[i]);enter;}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}