困困的开始了我的修炼树剖之旅途
考虑怎么搞这个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;
}
标签：剖分,int,ll,离线,++,maxn,lca,id From： https://www.cnblogs.com/liyishui2003/p/17270669.html