困困的开始了我的修炼树剖之旅途
考虑怎么搞这个lca
是说，习惯了倍增求lca，突然冒出这么一个东西还真不会搞
那要么能一次性求很多个lca(?)，要么把deep[lca(i,z)]这个东西转化一下
当我们不会倍增求lca的时候，有一个很朴素的想法就是把x到根节点一路上的点都染色
然后让y节点开始往上跳，遇到的第一个染色点就是lca
类似的，如果把x到根节点上的所有点加1，再求一遍y到根节点上的所有点的和
树上的区间加和求和都可以树剖(logn)做
那询问怎么处理？
观察到[l,r]的答案具有可加性，那么也可以差分了
把每个询问拆成两个，一个是{l-1,i,z,-1}，另一个是{r,i,z,1}
按端点sort一下，从1号点开始加到n号点，顺便求个和
l++,r++,z++; Q[i*2-1]=(Query){l-1,i,z,-1}; Q[i*2]=(Query){r,i,z,1}; } sort(Q+1,Q+2*m+1,cmp); int at=0; for(int i=1;i<=2*m;i++){ while(at<Q[i].r) addpath(1,++at,1); ans[Q[i].id]+=Q[i].sign*qpath(1,Q[i].x); }
有笨蛋处理输入的时候l++,r++,但是z没有++，是谁我不说(
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; typedef long long ll; const int maxn=2*int(1e5)+7; ll cnt=0,ecnt=0; ll n,m,R,id[maxn],wt[maxn],top[maxn],son[maxn],head[maxn],fa[maxn],siz[maxn],dep[maxn]; ll mod,a[maxn<<2],lazy[maxn<<2],w[maxn]; struct lys{ int from,to,nex; }e[maxn*2]; void addedge(int from,int to){ ecnt++;e[ecnt].from=from;e[ecnt].to=to;e[ecnt].nex=head[from];head[from]=ecnt; } void dfs1(int u,int f){ siz[u]=1; fa[u]=f; dep[u]=dep[f]+1; int maxson=-1; for(int i=head[u];i;i=e[i].nex){ int to=e[i].to; if(to==f) continue; dfs1(to,u); siz[u]+=siz[to]; if(siz[to]>maxson) son[u]=to,maxson=siz[to]; } } void dfs2(int u,int topf){ cnt++;// dfs order id[u]=cnt; wt[cnt]=w[u]; top[u]=topf; if(!son[u]) return; dfs2(son[u],topf); for(int i=head[u];i;i=e[i].nex){ int to=e[i].to; if(to==son[u]||to==fa[u]) continue; dfs2(to,to); } } void build(int rt,int l,int r){ if(l==r){ a[rt]=0;return; } int mid=(l+r)>>1; build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); a[rt]=a[rt<<1]+a[rt<<1|1]; } void pushdown(int rt,int l,int r){ if(lazy[rt]){ int mid=(l+r)>>1; lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; a[rt<<1]+=lazy[rt]*(mid-l+1); a[rt<<1|1]+=lazy[rt]*(r-mid); lazy[rt]=0; } } void add(int rt,int l,int r,int ql,int qr,ll k){ if(ql<=l&&r<=qr){ a[rt]+=(r-l+1)*k; lazy[rt]+=k; return; } int mid=(l+r)>>1; if(lazy[rt]) pushdown(rt,l,r); if(ql<=mid) add(rt<<1,l,mid,ql,qr,k); if(mid<qr) add(rt<<1|1,mid+1,r,ql,qr,k); a[rt]=a[rt<<1]+a[rt<<1|1]; } void addpath(int x,int y,ll k){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); add(1,1,n,id[top[x]],id[x],k); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); add(1,1,n,id[x],id[y],k); } ll query(int rt,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ return a[rt]; } pushdown(rt,l,r); int mid=(l+r)>>1; ll ans=0; if(mid>=ql) ans+=query(rt<<1,l,mid,ql,qr); if(mid<qr) ans+=query(rt<<1|1,mid+1,r,ql,qr); return ans; } ll qpath(int x,int y){ ll ans=0; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); ans+=query(1,1,n,id[top[x]],id[x]); x=fa[top[x]]; } if(dep[x]>dep[y]) swap(x,y); ans+=query(1,1,n,id[x],id[y]); return ans; } void addson(int u,ll k){ add(1,1,n,id[u],id[u]+siz[u]-1,k); } ll qson(int u){ return query(1,1,n,id[u],id[u]+siz[u]-1); } struct Query{ int r,id,x,sign; }Q[maxn*2]; bool cmp(Query a,Query b){ return a.r<b.r; } ll ans[maxn]; int main(){ //freopen("lys.in","r",stdin); fastio; cin>>n>>m; for(int i=2;i<=n;i++){ int father;cin>>father; father++;addedge(father,i); } dfs1(1,0); dfs2(1,1); build(1,1,n); for(int i=1;i<=m;i++){ int l,r,z; cin>>l>>r>>z; l++,r++,z++; Q[i*2-1]=(Query){l-1,i,z,-1}; Q[i*2]=(Query){r,i,z,1}; } sort(Q+1,Q+2*m+1,cmp); int at=0; for(int i=1;i<=2*m;i++){ while(at<Q[i].r) addpath(1,++at,1); ans[Q[i].id]+=Q[i].sign*qpath(1,Q[i].x); } for(int i=1;i<=m;i++) cout<<ans[i]%201314<<endl; }