初探树链剖分１
初探树链剖分.
可能更加考察线段树:|
学习资料
资料一
树链剖分详解 https://www.cnblogs.com/ivanovcraft/p/9019090.html
这个资料有三个例题 :
分别是
lugou p3384 [模板] 轻重链剖分
[NOI2015]软件包管理器
[SDOI2011]染色
资料二
树链剖分瞎入门 https://blog.csdn.net/dkacvenus/article/details/86171674
这个资料的例题还没做:｜
资料三
树链剖分讲解及总结（重链剖分＋长链剖分）https://www.cnblogs.com/Khada-Jhin/p/9576403.html
长链剖分还未学习，好像很难的样子，重点先看重链剖分
资料四
oi wiki https://oi-wiki.org/graph/hld/#_8
资料五
lca 讲的不错
https://www.cnblogs.com/2529102757ab/p/10727254.html
题目
ZJOI2008 树的统计
线段树类型： 单点更新，区间求最大值，区间求和
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int maxv=1e5+10;
const int maxn=maxv;
struct Edge{
int to,nxt;
}edge[maxv*2];
// 记得初始化
// mst(head,-1)
int head[maxn];
int tot=0;
void addedge(int from,int to){
edge[tot].to=to;
edge[tot].nxt=head[from];
head[from]=tot++;
}
int val[maxv];
int A[maxv];
int f[maxn]; //保存结点u的父亲结点
int d[maxn]; //保存结点u的深度值
int size[maxn]; //保存以u为根的子树节点个数
int son[maxn]; //保存重儿子
int rk[maxn]; //保存当前dfs标号在树中所对应的节点
int top[maxn]; //保存当前结点所在链的顶端节点
int id[maxn]; //保存树中每个结点剖分以后的新编号（dfs的执行顺序）
int cnt=0;
// get size son f d
// dfs1(root,0,1);
int dfs1(int u,int fa,int depth) // 当前节点、父亲节点、层次深度
{
f[u]=fa;
d[u]=depth;
size[u]=1;
int maxson=-1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa) continue;
size[u]+=dfs1(v,u,depth+1);
if(size[v]>maxson){
maxson=size[v];
son[u]=v;
}
}
return size[u];
}
// get rk top id
// 记得初始化cnt=0
// dfs2(root,root)
void dfs2(int u,int t) // 当前节点，重链顶端
{
top[u]=t;
id[u]=++cnt; //标记dfs序列
A[cnt]=val[u];
rk[cnt]=u; //序号cnt对应节点u
if(!son[u]) return;
dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v!=son[u] && v!=f[u])
dfs2(v,v);
}
}
struct Tree{
int sum,maxn,l,r;
}tree[maxv<<2];
#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
void pushup(int o){
tree[o].sum=tree[ls].sum+tree[rs].sum;
tree[o].maxn=max(tree[ls].maxn,tree[rs].maxn);
}
void build(int l,int r,int o){
tree[o].l=l,tree[o].r=r;
if(tree[o].l==tree[o].r){
tree[o].sum=tree[o].maxn=A[l];
return;
}
int m=(l+r)>>1;
build(lson);build(rson);
pushup(o);
}
void update(int k,int v,int o){
if(tree[o].l==tree[o].r){
tree[o].sum=tree[o].maxn=v;
return;
}
int m=(tree[o].l+tree[o].r)>>1;
if(k<=m) update(k,v,ls);
else update(k,v,rs);
pushup(o);
}
int qsum(int ql,int qr,int o){
if(ql<=tree[o].l && tree[o].r<=qr)
return tree[o].sum;
int m=(tree[o].l+tree[o].r)>>1;
int res=0;
if(ql<=m) res+=qsum(ql,qr,ls);
if(qr>m) res+=qsum(ql,qr,rs);
return res;
}
int qmax(int ql,int qr,int o){
if(ql<=tree[o].l && tree[o].r<=qr)
return tree[o].maxn;
int m=(tree[o].l+tree[o].r)>>1;
/*
if(qr<=m) return qmax(ql,qr,ls);
else if(ql>m) return qmax(ql,qr,rs);
else return max(qmax(ql,m,ls),qmax(m+1,qr,rs));
*/
int res=INT_MIN;
if(ql<=m) res=max(res,qmax(ql,qr,ls));
if(qr>m) res=max(res,qmax(ql,qr,rs));
return res;
}
int lca(int x,int y){
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
return x;
}
int fsum(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=qsum(id[top[x]],id[x],1);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans+=qsum(id[x],id[y],1);
return ans;
}
int fmax(int x,int y){
int ans=INT_MIN;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
ans=max(ans,qmax(id[top[x]],id[x],1));
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans=max(ans,qmax(id[x],id[y],1));
return ans;
}
int main(){
mst(head,-1);
tot=0;
int n;
scanf("%d",&n);
inc(i,1,n-1){
int a,b;scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
}
inc(i,1,n) scanf("%d",val+i);
dfs1(1,0,1);
dfs2(1,1);
build(1,n,1);
int q;scanf("%d",&q);
while(q--){
string ch;
int a,b;
cin>>ch>>a>>b;
// cout<<ch<<" "<<a<<" "<<b<<endl;
if(ch[1]=='M') printf("%d\n",fmax(a,b));
else if(ch[1]=='S') printf("%d\n",fsum(a,b));
else update(id[a],b,1);
}
return 0;
}lougu P2279 LCA
利用树剖解决LCA问题的需要技巧
我的代码
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
// 题目当中的点数为 5e5
// 个人推算 5e5就够了,但是会RE 3个点(共10个点吧)
//
// 因为之前tot和cnt混用了:| (都用的是cnt)
// 现在直接5e5就ac了
const int maxv=5e5+10;
struct Edge{
int to,nxt;
}edge[maxv*2];
int head[maxv];
int tot;
void addedge(int from,int to){
edge[tot].to=to;
edge[tot].nxt=head[from];
head[from]=tot++;
}
int f[maxv]; //保存结点u的父亲结点
int d[maxv]; //保存结点u的深度值
int size[maxv]; //保存以u为根的子树节点个数
int son[maxv]; //保存重儿子
int rk[maxv]; //保存当前dfs标号在树中所对应的节点
int top[maxv]; //保存当前结点所在链的顶端节点
int id[maxv]; //保存树中每个结点剖分以后的新编号（dfs的执行顺序）
int cnt;
// get size son f d
// cnt =0
// dfs1(root,0,1);
void dfs1(int u,int fa,int depth) // 当前节点、父亲节点、层次深度
{
f[u]=fa;
d[u]=depth;
size[u]=1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa) continue;
dfs1(v,u,depth+1);
size[u]+=size[v];
if(size[v]>size[son[u]])
son[u]=v;
}
}
// get rk top id
// dfs2(root,root)
void dfs2(int u,int t) // 当前节点，重链顶端
{
top[u]=t;
id[u]=++cnt; //标记dfs序列
rk[cnt]=u; //序号cnt对应节点u
if(!son[u]) return;
dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v!=son[u] && v!=f[u])
dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(d[top[u]]>d[top[v]])
u=f[top[u]];
else
v=f[top[v]];
}
return d[u]>d[v]? v: u;
}
int main(){
int n=read();
int m=read();
int s=read();
mst(head,-1);
tot=0;
// cnt=1;
inc(i,1,n-1){
int a=read();
int b=read();
addedge(a,b);
addedge(b,a);
}
cnt=0;
dfs1(s,0,1);
dfs2(s,s);
inc(i,1,m){
int a=read();
int b=read();
// cout<<a<<" "<<b<<endl;
cout<<lca(a,b)<<"\n";
}
return 0;
}JLOI 2014 松鼠的新家
利用差分，解决区间更新，最后做前缀和，得到每个点的值
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int maxv=3e5+10;
struct Edge{
int to,nxt;
}edge[maxv*2];
int head[maxv];
int tot=0;
void addedge(int from,int to){
edge[tot].to=to;
edge[tot].nxt=head[from];
head[from]=tot++;
}
int cnt;
int f[maxv]; //保存结点u的父亲结点
int d[maxv]; //保存结点u的深度值
int size[maxv]; //保存以u为根的子树节点个数
int son[maxv]; //保存重儿子
int rk[maxv]; //保存当前dfs标号在树中所对应的节点
int top[maxv]; //保存当前结点所在链的顶端节点
int id[maxv]; //保存树中每个结点剖分以后的新编号（dfs的执行顺序）
// get size son f d
// dfs1(root,0,1);
int dfs1(int u,int fa,int depth) // 当前节点、父亲节点、层次深度
{
f[u]=fa;
d[u]=depth;
size[u]=1;
int maxson=-1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa) continue;
size[u]+=dfs1(v,u,depth+1);
if(size[v]>maxson){
maxson=size[v];
son[u]=v;
}
}
return size[u];
}
// get rk top id
// dfs2(root,root)
void dfs2(int u,int t) // 当前节点，重链顶端
{
top[u]=t;
id[u]=++cnt; //标记dfs序列
rk[cnt]=u; //序号cnt对应节点u
if(!son[u]) return;
dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v!=son[u] && v!=f[u])
dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(d[top[u]]>d[top[v]])
u=f[top[u]];
else
v=f[top[v]];
}
return d[u]>d[v]? v: u;
}
int val[maxv];
void update(int l,int r,int v){
// cout<<"update "<<l<<" "<<r<<" "<<v<<endl;
val[l]+=v;
val[r+1]-=v;
return;
}
void foo(int x,int y){
update(id[x],id[x],-1);
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
update(id[top[x]],id[x],1);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
update(id[x],id[y],1);
return ;
}
int a[maxv];
int main(){
int n=read();
inc(i,1,n) scanf("%d",a+i);
mst(head,-1);
tot=0;
inc(i,1,n-1){
int a=read();
int b=read();
addedge(a,b);
addedge(b,a);
val[i]=0;
}
val[n]=0;
//---------------------------------------------------
cnt=0;
dfs1(1,0,1);
dfs2(1,1);
//---------------------------------------------------
//
update(id[a[1]],id[a[1]],1);
update(id[a[n]],id[a[n]],-1);
inc(i,1,n-1){
int fi=a[i];
int se=a[i+1];
foo(fi,se);
}
for(int i=0;i<=n;i++)
val[i+1]+=val[i];
int o=0;
for(int i=1;i<=n;i++){
int p=id[i];
printf("%d\n",val[p]);
}
return 0;
}HAOI2015 树上操作
线段树的类型： 区间更新，区间求和
//
// https://loj.ac/problem/2125
// ac
//
// 需要注意longlong
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
const int maxv=1e5+10;
struct Edge{
int to,nxt;
}edge[maxv*2];
int head[maxv];
int tot=0;
void addedge(int from,int to){
edge[tot].to=to;
edge[tot].nxt=head[from];
head[from]=tot++;
}
int cnt;
int f[maxv]; //保存结点u的父亲结点
int d[maxv]; //保存结点u的深度值
int size[maxv]; //保存以u为根的子树节点个数
int son[maxv]; //保存重儿子
int rk[maxv]; //保存当前dfs标号在树中所对应的节点
int top[maxv]; //保存当前结点所在链的顶端节点
int id[maxv]; //保存树中每个结点剖分以后的新编号（dfs的执行顺序）
int R[maxv];
// get size son f d
// dfs1(root,0,1);
int dfs1(int u,int fa,int depth) // 当前节点、父亲节点、层次深度
{
f[u]=fa;
d[u]=depth;
size[u]=1;
int maxson=-1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa) continue;
size[u]+=dfs1(v,u,depth+1);
if(size[v]>maxson){
maxson=size[v];
son[u]=v;
}
}
return size[u];
}
// get rk top id
// dfs2(root,root)
void dfs2(int u,int t) // 当前节点，重链顶端
{
top[u]=t;
id[u]=++cnt; //标记dfs序列
rk[cnt]=u; //序号cnt对应节点u
if(!son[u]) {
R[u]=cnt;
return;
}
dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v!=son[u] && v!=f[u])
dfs2(v,v);
}
R[u]=cnt;
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(d[top[u]]>d[top[v]])
u=f[top[u]];
else
v=f[top[v]];
}
return d[u]>d[v]? v: u;
}
int a[maxv];
struct Tree{
ll sum,add;
int l,r;
}tree[maxv<<2];
#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
void pushup(int o){
tree[o].sum=tree[ls].sum+tree[rs].sum;
}
void pushdown(int o,int len){
if(tree[o].add){
tree[ls].add+=tree[o].add;
tree[rs].add+=tree[o].add;
tree[ls].sum+=tree[o].add*(len-(len>>1));
tree[rs].sum+=tree[o].add*(len>>1);
tree[o].add=0;
}
}
void build(int l,int r,int o){
tree[o].l=l;
tree[o].r=r;
tree[o].add=0;
if(l==r){
tree[o].sum=1LL*a[rk[l]];
return;
}
int m=(l+r)>>1;
build(lson);build(rson);
pushup(o);
}
void update(int ql,int qr,ll v,int o){
int l=tree[o].l;
int r=tree[o].r;
if(ql<=l&&r<=qr){
tree[o].add+=v;
tree[o].sum+=v*(r-l+1);
return;
}
pushdown(o,r-l+1);
int m=(l+r)>>1;
if(ql<=m) update(ql,qr,v,ls);
if(qr>m) update(ql,qr,v,rs);
pushup(o);
}
ll query(int ql,int qr,int o){
int l=tree[o].l;
int r=tree[o].r;
if(ql<=l && r<=qr)
return tree[o].sum;
//if(ql<=tree[o].l && tree[o].r<=qr) return tree[o].sum;
pushdown(o,r-l+1);
int m=(l+r)>>1;
ll res=0;
if(ql<=m) res+=query(ql,qr,ls);
if(m<qr) res+=query(ql,qr,rs);
return res;
}
ll CAL(int x,int y=1){
ll ans=0;
while(top[x]!=top[y]) {
if(d[top[x]]<d[top[y]]) swap(x,y);
ans+=query(id[top[x]],id[x],1);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
ans+=query(id[x],id[y],1);
return ans;
}
int n,m;
int main(){
scanf("%d%d",&n,&m);
mst(head,-1);
inc(i,1,n) scanf("%d",a+i);
inc(i,1,n-1){
int fr=read();
int to=read();
addedge(fr,to);
addedge(to,fr);
}
cnt=0;
dfs1(1,0,1);
dfs2(1,1);
build(1,n,1);
for(int i=1;i<=m;i++){
int type=read();
/*
for(int i=1;i<=n;i++){
cout<<query(i,i,1)<<" ";
}
cout<<endl;
*/
if(type==1){
int x=read();
ll add=read();
update(id[x],id[x],add,1);
}else if(type==2){
int x=read();
int add=read();
//update(id[x],id[x]+size[x]-1,add,1);
update(id[x],R[x],add,1);
}else if(type==3){
int x=read();
ll res=CAL(x);
printf("%lld\n",res);
}
}
return 0;
}NOI2015 软件包管理器
用到的线段树的类型：
所有的值只有01，区间赋值，区间求和
（因为值只有０1所以处理细节区别于一般的线段树）
// https://uoj.ac/problem/128
//ID 题目 提交者 结果 用时 内存 语言 文件大小 提交时间
// #428100 #128. 【NOI2015】软件包管理器 ddy 100 3661ms 10968kb C++ 4.7kb 2020-08-24 22:39:54
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
char ch=getchar();int f=1,x=0;
while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
return f*x;
}
bool show=false;
// --------------------------------------------------------
// notice : 记得更改maxv的数量
const int maxv=1e5+10;
struct Edge{
int to,nxt;
}edge[maxv*2];
int head[maxv];
int tot=0;
void addedge(int from,int to){
edge[tot].to=to;
edge[tot].nxt=head[from];
head[from]=tot++;
}
int cnt;
int f[maxv]; //保存结点u的父亲结点
int d[maxv]; //保存结点u的深度值
int sz[maxv]; //保存以u为根的子树节点个数
int son[maxv]; //保存重儿子
int rk[maxv]; //保存当前dfs标号在树中所对应的节点
int top[maxv]; //保存当前结点所在链的顶端节点
int pos[maxv]; //保存树中每个结点剖分以后的新编号（dfs的执行顺序）
// get sz son f d
// dfs1(root,0,1);
int dfs1(int u,int fa,int depth) // 当前节点、父亲节点、层次深度
{
f[u]=fa;
d[u]=depth;
sz[u]=1;
int maxson=-1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa) continue;
sz[u]+=dfs1(v,u,depth+1);
if(sz[v]>maxson){
maxson=sz[v];
son[u]=v;
}
}
return sz[u];
}
// get rk top pos
// dfs2(root,root)
void dfs2(int u,int t) // 当前节点，重链顶端
{
top[u]=t;
pos[u]=++cnt; //标记dfs序列
rk[cnt]=u; //序号cnt对应节点u
if(!son[u]) return;
dfs2(son[u],t);
/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].to;
if(v!=son[u] && v!=f[u])
dfs2(v,v);
}
}
int lca(int u,int v){
while(top[u]!=top[v]){
if(d[top[u]]>d[top[v]])
u=f[top[u]];
else
v=f[top[v]];
}
return d[u]>d[v]? v: u;
}
struct Tree{
int sum,val;
int l,r;
}tree[maxv<<2];
#define o rt
#define ls o<<1
#define rs o<<1|1
#define lson l,m,ls
#define rson m+1,r,rs
void pushup(int o){
tree[o].sum=tree[ls].sum+tree[rs].sum;
}
void pushdown(int o,int len){
if(tree[o].val==-1) return;
int v=tree[o].val;
tree[ls].val=v;
tree[rs].val=v;
tree[ls].sum=(len-(len>>1))*v;
tree[rs].sum=(len>>1)*v;
tree[o].val=-1;
return;
}
void build(int l,int r,int o){
tree[o].l=l;
tree[o].r=r;
tree[o].val=-1;
if(l==r){
tree[o].sum=0;
return;
}
int m=(l+r)>>1;
build(lson);build(rson);
pushup(o);
}
void update(int ql,int qr,int v,int o){
int l=tree[o].l;
int r=tree[o].r;
if(ql<=l&&r<=qr){
tree[o].val=v;
tree[o].sum=v*(r-l+1);
return;
}
pushdown(o,r-l+1);
int m=(l+r)>>1;
if(ql<=m) update(ql,qr,v,ls);
if(qr>m) update(ql,qr,v,rs);
pushup(o);
}
int query(int ql,int qr,int o){
int l=tree[o].l;
int r=tree[o].r;
if(ql<=l && r<=qr)
return tree[o].sum;
pushdown(o,r-l+1);
int m=(l+r)>>1;
int res=0;
if(ql<=m) res+=query(ql,qr,ls);
if(m<qr) res+=query(ql,qr,rs);
return res;
}
ll install(int x,int y=1){
int xx=x;
ll ans=0;
while(top[x]!=top[y]){
if(d[top[x]]<d[top[y]]) swap(x,y);
if(show)
cout<<pos[top[x]]<<" "<<pos[x]<<endl;
ans+=query(pos[top[x]],pos[x],1);
if(show)
cout<<ans<<endl;
update(pos[top[x]],pos[x],1,1);
x=f[top[x]];
}
if(d[x]>d[y]) swap(x,y);
if(show)
cout<<pos[x]<<" "<<pos[y]<<endl;
ans+=query(pos[x],pos[y],1);
update(pos[x],pos[y],1,1);
if(show){
cout<<"ans "<<ans<<endl;
cout<<"d[x] "<<d[x]<<endl;
cout<<"x "<<x<<endl;
cout<<d[x]<<endl;
}
return d[xx]-ans;
}
int uninstall(int x){
int o=query(pos[x],pos[x]+sz[x]-1,1);
update(pos[x],pos[x]+sz[x]-1,0,1);
return o;
}
int n,m;
int main(){
scanf("%d",&n);
inc(i,1,n) head[i]=-1;
tot=0;
inc(i,2,n){
int x;scanf("%d",&x);x++;
addedge(i,x);
addedge(x,i);
}
//---------------------------------------------------
cnt=0;
int r=1;
dfs1(r,0,1);
dfs2(r,r);
//---------------------------------------------------
build(1,n,1);
scanf("%d",&m);
while(m--){
char ch[20];int x;
scanf("%s %d",ch,&x);x++;
if(ch[0]=='i') {
int o=install(x);
printf("%d\n",o);
}else if(ch[0]=='u'){
int o=uninstall(x);
printf("%d\n",o);
}
if(show){
for(int i=1;i<=n;i++){
cout<<query(i,i,1)<<" ";
}
cout<<endl;
}
}
return 0;
}本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！