本文共 2574 字，大约阅读时间需要 8 分钟。
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
第一行2个整数n q。
输出q行，每行表示一个询问的答案。每个答案对201314取模输出
共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。
两个点a,b的lca的深度就是dep[lca]，如果暴力地写这道题就是对于每个x与[l,r]内所有数的lca都求一遍，但可以发现lca还有一种求法：对于i,x两点的lca，可以把i到根节点路径上所有的边权+1(刚开始都是零)，只要再求x到根节点上的路径和就是lca的深度。那么对于[l,r]内所有的点和x的lca，只要把每个点到根的路径上边权都+1，然后再求x到根的路径和就好了。这个只要树链剖分加线段树就能维护，每次修改和查询在树上边跳边在线段树中操作就行了。但对于每次询问都要把线段树清空再重新标记，显然还是不行的，因此可以离线来做。我们发现求的东西具有可减性，即求[l,r]与x的lca深度和等于求[1,r]与x的lca深度和-[1,l-1]与x的lca深度和。因此每个询问可以拆成两部分，然后把所有查询排序，按节点标号顺序对到根路径上的边+1，每到一个点处理这个点处对应的查询。注意点的编号从零开始。
#include #include #include #include #include #include #include #include #include #include #define ll long longusing namespace std;int x;int l,r;int n,m;int tot;int num;int cnt;int f[100010];int d[100010];int s[100010];bool g[100010];int a[1000010];int to[100010];ll sum[800010];ll ans[100010];int top[100010];int son[100010];int size[100010];int head[100010];int next[100010];struct node{ int x; int l; int id;}q[200010];bool cmp(node a,node b){ return a.l size[son[x]]) { son[x]=to[i]; } }}void dfs2(int x,int tp){ s[x]=++num; top[x]=tp; if(son[x]) { dfs2(son[x],tp); } for(int i=head[x];i;i=next[i]) { if(to[i]!=son[x]) { dfs2(to[i],to[i]); } }}void pushup(int rt){ sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void pushdown(int rt,int l,int r){ if(a[rt]) { int mid=(l+r)>>1; a[rt<<1]+=a[rt]; a[rt<<1|1]+=a[rt]; sum[rt<<1]+=1ll*a[rt]*(mid-l+1); sum[rt<<1|1]+=1ll*a[rt]*(r-mid); a[rt]=0; }}void change(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) { a[rt]++; sum[rt]+=1ll*(r-l+1); return ; } pushdown(rt,l,r); int mid=(l+r)>>1; if(L<=mid) { change(rt<<1,l,mid,L,R); } if(R>mid) { change(rt<<1|1,mid+1,r,L,R); } pushup(rt);}ll query(int rt,int l,int r,int L,int R){ if(L<=l&&r<=R) { return sum[rt]; } pushdown(rt,l,r); int mid=(l+r)>>1; ll res=0; if(L<=mid) { res+=query(rt<<1,l,mid,L,R); } if(R>mid) { res+=query(rt<<1|1,mid+1,r,L,R); } return res;}void updata(int x){ while(top[x]!=1) { change(1,1,n,s[top[x]],s[x]); x=f[top[x]]; } change(1,1,n,1,s[x]);}ll downdata(int x){ ll res=0; while(top[x]!=1) { res+=query(1,1,n,s[top[x]],s[x]); x=f[top[x]]; } res+=query(1,1,n,1,s[x]); return res;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i
转载于:https://www.cnblogs.com/Khada-Jhin/p/9568645.html
转载地址：https://blog.csdn.net/weixin_30621711/article/details/94765147 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
