NOI2015的试题，一道树链剖分的模板题
主要过程：树剖完成后对线段树进行区间修改，区间查询。
代码较长，很考验代码能力
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 typedef long long ll; 5 inline int abs(int x) { 6 return x>0?x:-x; 7 } 8 inline int read() { 9 int ret=0,f=1; 10 char c=getchar(); 11 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();} 12 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 13 return ret*f; 14 } 15 using namespace std; 16 int n,q; 17 struct edge { 18 int next,to; 19 }a[100010<<1]; 20 int num,head[100010<<1]; 21 char in[100]; 22 inline void add(int from,int to) { 23 a[++num].next=head[from]; a[num].to=to; head[from]=num; 24 swap(from,to); 25 a[++num].next=head[from]; a[num].to=to; head[from]=num; 26 } 27 int fa[100010],d[100010],seg[100010],rev[100010],top[100010],son[100010]; 28 int data[100010<<2],tag[100010<<2],size[100010]; 29 void dfs1(int u,int f) { 30 d[u]=d[f]+1; 31 fa[u]=f; 32 size[u]=1; 33 for(int i=head[u];i;i=a[i].next) { 34 int v=a[i].to; 35 if(v==f) continue ; 36 dfs1(v,u); 37 size[u]+=size[v]; 38 if(size[v]>size[son[u]]) son[u]=v; 39 } 40 } 41 void dfs2(int u,int fa) { 42 if(son[u]) { 43 seg[son[u]]=++seg[0]; 44 rev[seg[0]]=son[u]; 45 top[son[u]]=top[u]; 46 dfs2(son[u],u); 47 } 48 for(int i=head[u];i;i=a[i].next) { 49 int v=a[i].to; 50 if(!top[v]) { 51 seg[v]=++seg[0]; 52 top[v]=v; 53 rev[seg[0]]=v; 54 dfs2(v,u); 55 } 56 } 57 } 58 void build(int now,int l,int r) { 59 tag[now]=-1; 60 if(l==r) { 61 tag[now]=data[now]=0; 62 return ; 63 } 64 int mid=l+r>>1; 65 build(now<<1,l,mid); 66 build(now<<1|1,mid+1,r); 67 } 68 void pushdown(int now,int len) { 69 if(tag[now]==-1) return ; 70 tag[now<<1]=tag[now<<1|1]=tag[now]; 71 data[now<<1]=tag[now]*(len-(len>>1)); 72 data[now<<1|1]=tag[now]*(len>>1); 73 tag[now]=-1; 74 } 75 void updata(int now,int l,int r,int x,int y,int val) { 76 if(x<=l&&r<=y) { 77 tag[now]=val; 78 data[now]=val*(r-l+1); 79 return ; 80 } 81 pushdown(now,r-l+1); 82 int mid=l+r>>1; 83 if(x<=mid) updata(now<<1,l,mid,x,y,val); 84 if(y>mid) updata(now<<1|1,mid+1,r,x,y,val); 85 data[now]=data[now<<1]+data[now<<1|1]; 86 } 87 void find(int x,int y) { 88 while(top[x]!=top[y]) { 89 if(d[top[x]]<d[top[y]]) swap(x,y); 90 updata(1,1,seg[0],seg[top[x]],seg[x],1); 91 x=fa[top[x]]; 92 } 93 if(d[x]>d[y]) swap(x,y); 94 updata(1,1,seg[0],seg[x],seg[y],1); 95 } 96 int main() { 97 n=read(); 98 for(int i=2;i<=n;i++) add(i,read()+1); 99 dfs1(1,0); 100 seg[0]=seg[1]=rev[1]=top[1]=1; 101 dfs2(1,0); 102 build(1,1,seg[0]); 103 q=read(); 104 while(q--) { 105 scanf("%s",in+1); 106 int x=read()+1; 107 if(in[1]=='i') { 108 int sum1=data[1]; 109 find(1,x); 110 int sum2=data[1]; 111 printf("%d ",abs(sum1-sum2)); 112 } 113 else { 114 int sum1=data[1]; 115 updata(1,1,seg[0],seg[x],seg[x]+size[x]-1,0); 116 int sum2=data[1]; 117 printf("%d ",abs(sum1-sum2)); 118 } 119 } 120 return 0; 121 }
注意线段树的标记操作