呀,我又来骗访问了QAQ

其实就是刨的模板题,不过题面真tm长

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;

struct segment_tree { int l,r,w,tag; } SGT[400100]={0};
struct ed { int pre,to; } edge[200010]={0};
int nodenum,fx,tx,at=0,pointer[100010]={0};

int topx[100010]={0},hson[100010]={0},anc[100010]={0},tsize[100010]={0};
int depth[100010]={0},dfn[100010]={0},tstamp=0;

int lx,rx,val;
char chs[10]={0};

inline void readx(int& x)
{
	x=0; int k=1; register char ch=0;
	while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; }
	while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
	x*=k;
}

inline void Insert()
{
	at++;
	edge[at].pre=pointer[fx];
	edge[at].to=tx;
	pointer[fx]=at;
	at++;
	edge[at].pre=pointer[tx];
	edge[at].to=fx;
	pointer[tx]=at;
}

inline void Fancy(int nownode,int nowdep,int fa)
{
	depth[nownode]=nowdep; anc[nownode]=fa; tsize[nownode]=1;
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
	{
		if (edge[prex].to!=fa)
		{
			Fancy(edge[prex].to,nowdep+1,nownode);
			tsize[nownode]+=tsize[edge[prex].to];
			if (tsize[hson[nownode]]<tsize[edge[prex].to]) hson[nownode]=edge[prex].to;
		}
	}
}
inline void Dreams(int nownode,int src)
{
	topx[nownode]=src; dfn[nownode]=++tstamp;
	if (hson[nownode]) Dreams(hson[nownode],src);
	for (int prex=pointer[nownode];prex;prex=edge[prex].pre)
		if (edge[prex].to!=anc[nownode] && edge[prex].to!=hson[nownode]) Dreams(edge[prex].to,edge[prex].to);
}

inline void BuildTree(int lxx,int rxx,int inx)
{
	SGT[inx].l=lxx; SGT[inx].r=rxx;
	if (lxx==rxx) return;
	int mid=(lxx+rxx)>>1;
	BuildTree(lxx,mid,inx<<1);
	BuildTree(mid+1,rxx,inx<<1|1);
}
inline void pushdown(int inx)
{
	SGT[inx<<1].tag=SGT[inx<<1|1].tag=SGT[inx].tag;
	if (SGT[inx].tag==1) SGT[inx<<1].w=SGT[inx<<1|1].w=0;
	if (SGT[inx].tag==2)
	{
		SGT[inx<<1].w=(SGT[inx<<1].r-SGT[inx<<1].l+1);
		SGT[inx<<1|1].w=(SGT[inx<<1|1].r-SGT[inx<<1|1].l+1);
	}
	SGT[inx].tag=0;
}
inline void update(int inx)
{
	if (SGT[inx].l>=lx && SGT[inx].r<=rx)
	{
		SGT[inx].w=val*(SGT[inx].r-SGT[inx].l+1);
		SGT[inx].tag=val+1;
		return;
	}
	if (SGT[inx].tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)>>1;
	if (lx<=mid) update(inx<<1);
	if (rx>mid) update(inx<<1|1);
	SGT[inx].w=SGT[inx<<1].w+SGT[inx<<1|1].w;
}
inline int query(int inx)
{
	if (SGT[inx].l>=lx && SGT[inx].r<=rx) return SGT[inx].w;
	if (SGT[inx].tag) pushdown(inx);
	int mid=(SGT[inx].l+SGT[inx].r)>>1,ret=0;
	if (lx<=mid) ret+=query(inx<<1);
	if (rx>mid) ret+=query(inx<<1|1);
	SGT[inx].w=SGT[inx<<1].w+SGT[inx<<1|1].w;
	return ret;
}

inline int solve_subt(int u)//uninstall some software
{
	lx=dfn[u]; rx=dfn[u]+tsize[u]-1;
	int ans=query(1);
	val=0; update(1);
	return ans;
}

inline int solve_range(int u)//install new software
{
	int ret=0; val=1;
	while (topx[u]!=1)
	{
		lx=dfn[topx[u]]; rx=dfn[u];
		ret+=(depth[u]-depth[topx[u]]+1-query(1));
		update(1);
		u=anc[topx[u]];
	}
	lx=1; rx=dfn[u]; 
	ret+=(depth[u]-query(1));
	update(1);
	return ret;
}

int main()
{
	readx(nodenum);
	for (int i=2;i<=nodenum;i++) { tx=i; readx(fx); fx++; Insert(); }
	
	Fancy(1,1,-1); Dreams(1,1);
	BuildTree(1,tstamp,1);
	
	int opt,ux; readx(opt);
	for (int i=1;i<=opt;i++)
	{
		scanf("%s",chs); readx(ux); ux++;
		if (chs[0]=='u') printf("%d\n",solve_subt(ux));
		else printf("%d\n",solve_range(ux));
	}
	return 0;
}

 

分类: 树剖

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.