#include<bits/stdc++.h> using namespace std; const int mx=1e5+1; int n,Q,x,y,d[mx],fa[mx],siz[mx],ev[mx],a[mx],son[mx],dfn[mx],cnt,id[mx],top[mx],ans[mx]; struct edge{int c,w,id,u,v;}e[mx*2]; struct que{int u,v,x,y;}q[mx*2]; struct tree{int l,r,lzy1,lzy2;}t[mx*4]; vector<edge> v[mx]; vector<int> es[mx]; vector<int> qs[mx]; //以下树剖 void dfs1(int f,int u) { d[u]=d[f]+1,fa[u]=f,siz[u]=1; int len=v[u].size(); for(int i=0;i<len;i++) { edge next=v[u][i]; int nv=next.v; if(nv==f) continue; ev[next.id]=nv,a[nv]=next.w; dfs1(u,nv); siz[u]+=siz[nv]; if(siz[nv]>siz[son[u]]) son[u]=nv; } } void dfs2(int f,int u) { dfn[u]=++cnt,id[cnt]=u,top[u]=f; if(son[u]) dfs2(f,son[u]); int len=v[u].size(); for(int i=0;i<len;i++) { int nv=v[u][i].v; if(nv==fa[u] || nv==son[u]) continue; dfs2(nv,nv); } } //以上树剖 //以下线段树 void pushup1(int x){t[x].lzy1=t[x<<1].lzy1+t[x<<1|1].lzy1;} void pushup2(int x){t[x].lzy2=t[x<<1].lzy2+t[x<<1|1].lzy2;} void build(int x,int l,int r) { t[x].l=l,t[x].r=r; if(l==r) { t[x].lzy1=a[id[l]],t[x].lzy2=0; return; } int mid=(l+r)/2; build(x<<1,l,mid);build(x<<1|1,mid+1,r); pushup1(x); } void chang1(int x,int obx,int w) { if(t[x].l==t[x].r){t[x].lzy1=w;return;} int mid=(t[x].l+t[x].r)>>1; if(obx<=mid) chang1(x<<1,obx,w); else chang1(x<<1|1,obx,w); pushup1(x); } void chang2(int x,int obx,int w) { if(t[x].l==t[x].r){t[x].lzy2=w;return;} int mid=(t[x].l+t[x].r)>>1; if(obx<=mid) chang2(x<<1,obx,w); else chang2(x<<1|1,obx,w); pushup2(x); } int find1(int x,int l,int r) { if(l<=t[x].l && r>=t[x].r) return t[x].lzy1; int mid=(l+r)>>1,s=0; if(l<=mid) s+=find1(x<<1,l,r); if(r>mid) s+=find1(x<<1|1,l,r); return s; } int find2(int x,int l,int r) { if(l<=t[x].l && r>=t[x].r) return t[x].lzy2; int mid=(l+r)>>1,s=0; if(l<=mid) s+=find2(x<<1,l,r); if(r>mid) s+=find2(x<<1|1,l,r); return s; } //以上线段树 int fans(int x,int y,int k) { int ans=0; while(top[x]!=top[y]) { if(d[top[x]]<d[top[y]]) swap(x,y); ans+=find1(1,dfn[top[x]],dfn[x]); ans+=find2(1,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]>d[y]) swap(x,y); if(x!=y) { ans+=find1(1,dfn[x]+1,dfn[y]); ans+=k*find2(1,dfn[x]+1,dfn[y]); } return ans; } int main() { cin >> n >> Q; for(int i=1;i<n;i++) { cin >> e[i].u >> e[i].v >> e[i].c >> e[i].w; e[i].id=i; v[e[i].u].push_back({e[i].u,e[i].v,e[i].c,e[i].w,e[i].id}); v[e[i].v].push_back({e[i].v,e[i].u,e[i].c,e[i].w,e[i].id}); es[e[i].c].push_back(i); } for(int i=1;i<=Q;i++) { cin >> q[i].x >> q[i].y >> q[i].u >> q[i].v; qs[q[i].x].push_back(i); } dfs1(1,1);dfs2(1,1);build(1,1,n); for(int i=1;i<n;i++) { int len=es[i].size(); for(int j=0;j<len;j++) { int k=ev[es[i][j]]; find1(1,dfn[k],0); find2(1,dfn[k],1); } for(int j=0;j<len;j++) { int k=qs[i][j]; ans[k]=fans(q[k].u,q[k].v,q[k].y); } for(int j=0;j<len;j++) { int k=ev[es[i][j]]; find1(1,dfn[k],e[es[i][j]].w); find2(1,dfn[k],0); } } for(int i=1;i<=Q;i++) cout<<ans[i]<<"\n"; return 0; }
时间: 2023-11-25 20:06:16 浏览: 72
c++万能头文件(包含所有其他头文件)#include<bits/stdc++.h> 注:此cpp文件包含万能头文件以及基本框架
5星 · 资源好评率100%
这段代码的主要功能是树剖和线段树结合实现树上路径查询。
在运行代码时,需要输入两个整数 n 和 Q,分别表示树的节点数和查询的数量。接下来输入 n-1 行数据,每行包含四个整数 u、v、c、w,表示树上的一条边,其中 u 和 v 是边的两个节点,c 是边的编号,w 是边的权值。然后输入 Q 行数据,每行包含四个整数 x、y、u、v,表示一个查询,询问从节点 x 到节点 y 的路径上,编号为 u 的边出现了多少次,并且编号为 u 的边的权值为 v。
代码首先进行树剖操作,计算出每个节点的深度、父节点、子树大小等信息。然后构建线段树,并使用线段树维护每个节点的信息。接下来,根据边的编号进行预处理,计算出每条边所在节点的信息,并更新线段树。最后,根据查询进行路径计算,并输出结果。
这段代码看起来比较复杂,涉及到树剖和线段树等知识。如果你有具体的问题或者需要进一步解释,请告诉我。
阅读全文