不知为何每次一看到树链第k个相关的问题就一副这道题我之前做过的感觉，然后又找不到这题-_-
这题的话，对于第i年的询问，相当于有效的修改操作是到第i年为止的所有修改操作减去到第l年为止的所有修改操作，链剖加主席树维护一下修改操作然后用链剖在树上爬就行了……比较麻烦，代码写的很丑-_-
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 100010 #define MAXM 10000010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long struct vec{ int to; int fro; }; vec mp[MAXN]; int tai[MAXN],cnt; int RT; int fa[MAXN],SON[MAXN],siz[MAXN],dep[MAXN],tp[MAXN],dfn[MAXN],ndf[MAXN],tim; int n,m; int rt[MAXM],son[MAXM][2],v[MAXM]; int tot; int dt[MAXN]; int TOT,k; inline void be(int x,int y){ mp[++cnt].to=y; mp[cnt].fro=tai[x]; tai[x]=cnt; } inline void bde(int x,int y){ be(x,y); be(y,x); } void dfs(int x){ int i,y; siz[x]=1; dep[x]=dep[fa[x]]+1; for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; dfs(y); siz[x]+=siz[y]; if(siz[y]>siz[SON[x]]){ SON[x]=y; } } } void dfs2(int x,int z){ int i,y; dfn[x]=++tim; ndf[tim]=x; tp[x]=z; if(SON[x]){ dfs2(SON[x],z); for(i=tai[x];i;i=mp[i].fro){ y=mp[i].to; if(!dfn[y]){ dfs2(y,y); } } } } void change(int &x,int xx,int y,int z,int p){ x=++tot; v[x]=v[xx]+1; memcpy(son[x],son[xx],sizeof(son[x])); if(y==z){ return ; } int mid=y+z>>1; if(p<=mid){ change(son[x][0],son[xx][0],y,mid,p); }else{ change(son[x][1],son[xx][1],mid+1,z,p); } } int ask(int x,int xx,int y,int z,int l,int r){ if(y==l&&z==r){ return v[x]-v[xx]; } int mid=y+z>>1; if(r<=mid){ return ask(son[x][0],son[xx][0],y,mid,l,r); }else if(l>mid){ return ask(son[x][1],son[xx][1],mid+1,z,l,r); }else{ return ask(son[x][0],son[xx][0],y,mid,l,mid)+ask(son[x][1],son[xx][1],mid+1,z,mid+1,r); } } int lca(int x,int y,int X,int XX){ TOT=0; while(tp[x]!=tp[y]){ if(dep[tp[x]]<dep[tp[y]]){ swap(x,y); } TOT+=dep[x]-dep[tp[x]]+1-ask(rt[X],rt[XX],1,n,dfn[tp[x]],dfn[x]); x=fa[tp[x]]; } if(dep[x]>dep[y]){ swap(x,y); } TOT+=dep[y]-dep[x]+1-ask(rt[X],rt[XX],1,n,dfn[x],dfn[y]); return x; } void find(int x,int xx,int y,int z,int l,int r){ if(y==l&&z==r){ if(z-y+1-v[x]+v[xx]<k){ k-=z-y+1-v[x]+v[xx]; return ; } if(y==z){ k=0; printf("%d\n",ndf[y]); return ; } int mid=y+z>>1; int t=z-mid-v[son[x][1]]+v[son[xx][1]]; if(t>=k){ find(son[x][1],son[xx][1],mid+1,z,mid+1,r); }else{ k-=t; find(son[x][0],son[xx][0],y,mid,l,mid); } return ; } int mid=y+z>>1; if(r<=mid){ find(son[x][0],son[xx][0],y,mid,l,r); }else if(l>mid){ find(son[x][1],son[xx][1],mid+1,z,l,r); }else{ find(son[x][1],son[xx][1],mid+1,z,mid+1,r); if(k){ find(son[x][0],son[xx][0],y,mid,l,mid); } } } void tofind(int x,int y,int X,int XX){ while(tp[x]!=tp[y]){ int t=dep[x]-dep[tp[x]]+1-ask(rt[X],rt[XX],1,n,dfn[tp[x]],dfn[x]); if(t<k){ k-=t; TOT-=t; }else{ find(rt[X],rt[XX],1,n,dfn[tp[x]],dfn[x]); if(!k){ return; } } x=fa[tp[x]]; } int t=dep[x]-dep[y]+1-ask(rt[X],rt[XX],1,n,dfn[y],dfn[x]); if(t<k){ k-=t; TOT-=t; }else{ find(rt[X],rt[XX],1,n,dfn[y],dfn[x]); } } int main(){ int i,o,x,y,l; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&fa[i]); if(!fa[i]){ RT=i; }else{ be(fa[i],i); } } dfs(RT); dfs2(RT,RT); scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d",&o); rt[i]=rt[i-1]; if(o==1){ scanf("%d",&x); dt[x]=i; change(rt[i],rt[i],1,n,dfn[x]); } if(o==2){ scanf("%d%d%d%d",&x,&y,&k,&l); k+=(dt[x]<=l); int L=lca(x,y,i,l); if(k>TOT||(k==TOT&&dt[y]<=l)){ printf("-1\n"); continue ; } tofind(x,L,i,l); if(k){ k=TOT-k+1; tofind(y,L,i,l); } } } return 0; } /* 5 0 1 1 1 3 5 1 5 2 4 2 1 0 1 4 2 1 4 1 2 1 3 */
