初探树链剖分1

初探树链剖分.

可能更加考察线段树:|

学习资料

资料一

树链剖分详解 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,区间赋值,区间求和 

(因为值只有01所以处理细节区别于一般的线段树)

// 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 协议 ,转载请注明出处!