据说是个树链剖分裸题。。
嗯是个裸题。。
每个点再记个子树里面最后一条边在线段树里的位置。
完了。
不知道树链剖分的话：树链剖分就是用一些鬼畜的方法在树上套线段树。
给个学习链接：http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
然后代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
// <manager.cpp> - 01/01/16 11:47:34 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define m ((l+r)>>1) #define lq x<<1,l,m #define rq x<<1|1,m+1,r #define Q 1,1,tot const int MAXN=100001; int siz[MAXN],dep[MAXN],top[MAXN],f[MAXN],son[MAXN],w[MAXN],en[MAXN]; int tot; vector <int> b[MAXN]; struct st{ int val,lazy; }t[MAXN<<3]; void dfs1(int x){ siz[x]=1;son[x]=0; for(int i=0;i<b[x].size();i++){ int next=b[x][i]; dep[next]=dep[x]+1; f[next]=x; dfs1(next); siz[x]+=siz[next]; if(!son[x]||siz[son[x]]<siz[next])son[x]=next; } } void dfs2(int x,int y){ w[x]=++tot;top[x]=y; if(son[x])dfs2(son[x],y); for(int i=0;i<b[x].size();i++){ if(b[x][i]==son[x])continue; dfs2(b[x][i],b[x][i]); } en[x]=tot; } void build(int x,int l,int r){ t[x].val=0; t[x].lazy=-1; if(l==r)return; build(lq);build(rq); } void down(int x,int l,int r){ t[x<<1].lazy=t[x<<1|1].lazy=t[x].lazy; t[x].lazy=-1; } void up(int x,int l,int r){ if(t[x].lazy!=-1)t[x].val=t[x].lazy*(r-l+1); else t[x].val=t[x<<1].val+t[x<<1|1].val; } int query(int x,int l,int r,int ll,int rr,int p){ if(ll<=l&&r<=rr){ if(p)return r-l+1-t[x].val; return t[x].val; } int k=0; if(t[x].lazy!=-1)down(x,l,r); up(lq),up(rq); if(ll<=m)k+=query(lq,ll,rr,p); if(rr>m)k+=query(rq,ll,rr,p); return k; } void change(int x,int l,int r,int ll,int rr,int p){ if(ll<=l&&r<=rr){ t[x].lazy=p; up(x,l,r); return; } if(t[x].lazy!=-1)down(x,l,r); if(ll<=m)change(lq,ll,rr,p); else up(lq); if(rr>m)change(rq,ll,rr,p); else up(rq); up(x,l,r); } int install(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(dep[x]<dep[y])swap(x,y); ans+=query(Q,w[top[x]],w[x],1); change(Q,w[top[x]],w[x],1); x=f[top[x]]; } if(dep[x]<dep[y])swap(x,y); ans+=query(Q,w[top[x]],w[x],1); change(Q,w[top[x]],w[x],1); return ans; } int uninstall(int x){ int ans=query(Q,w[x],en[x],0); change(Q,w[x],en[x],0); return ans; } int main(){ freopen("manager.in","r",stdin); freopen("manager.out","w",stdout); int n=getint(); for(int i=1;i<n;i++)b[getint()].push_back(i); dfs1(0);dfs2(0,0);build(1,1,tot); int q=getint(); string ask; while(q--){ cin>>ask;int x=getint(); if(ask[0]=='i')printf("%d\n",install(0,x)); else printf("%d\n",uninstall(x)); } return 0; } |
说点什么