[HNOI2015] 开店
程序员文章站
2023-01-02 18:34:58
~~「前言」为防止在某巨巨的毒瘤idea 紫荆花之“店" 面前一脸懵,特滚来补此题。~~ ~~我还是太naive了。~~ 「题义」给出一棵单点度数很小的无根带边权、点权的树,每次询问在所有点权在\[l,r\]的点到c的距离之和。 「分析」考虑建立点分树,分治结构每个点都储存对应分治范围(简称范围)内 ......
「前言」为防止在某巨巨的毒瘤idea 紫荆花之“店" 面前一脸懵,特滚来补此题。 我还是太naive了。
「题义」给出一棵单点度数很小的无根带边权、点权的树,每次询问在所有点权在[l,r]的点到c的距离之和。
「分析」考虑建立点分树,分治结构每个点都储存对应分治范围(简称范围)内的信息,询问时从c向后跳分治链,并逐级将信息合并得到整棵树的答案。
对于链上某一点x,设前一个点为px,显然我们需要用到的,x范围中(除去px范围)的所有合法的点(即点权在[l,r]内的点)到c的距离之和,拆开为这些点到x的距离和+这些点的个数乘以x到c的距离。对于第一部分我们将它看作x范围内所有点到x的距离和-px范围内所有点到x的距离和,第二部分同理。
这样,我们只需要对每个节点x储存范围内所有点点权age、到x的距离dis以及到上一级分治中心fa[x]的距离ldis(放在集合d[x])。然后将d[x]按照age排序,那么x的分治范围对于查询中心c的产生贡的点献处于d[x]的一段区间上。利用前(后)缀和+二分就能地很好处理了。
#include <bits/stdc++.h> #define il inline #define ll long long using namespace std; const int n=150010; const int inf=0x3f3f3f3f; int n,q,a,age[n]; int head[n],to[n<<1],last[n<<1],len[n<<1]; il void addedge(int x,int y,int w) { static int cnt=0; to[++cnt]=y,len[cnt]=w,last[cnt]=head[x],head[x]=cnt; to[++cnt]=x,len[cnt]=w,last[cnt]=head[y],head[y]=cnt; } namespace dbl { int fa[n][20],dep[n]; ll ds[n][20]; void prdfs(int x,int d) { dep[x]=dep[fa[x][0]=d]+1; for(int i=1; (1<<i)<=dep[x]; ++i) { fa[x][i]=fa[fa[x][i-1]][i-1]; ds[x][i]=ds[fa[x][i-1]][i-1]+ds[x][i-1]; } for(int i=head[x]; i; i=last[i]) { if(to[i]!=d) ds[to[i]][0]=len[i],prdfs(to[i],x); } } il ll gtdis(int x,int y) { if(dep[x]<dep[y]) swap(x,y); ll ret=0; int dif=dep[x]-dep[y]; for(int i=19; ~i; --i) if((dif>>i)&1) ret+=ds[x][i],x=fa[x][i]; if(x==y) return ret; for(int i=19; ~i; --i) if(fa[x][i]!=fa[y][i]) ret+=ds[x][i],x=fa[x][i],ret+=ds[y][i],y=fa[y][i]; return ret+ds[x][0]+ds[y][0]; } } namespace dpd { struct node { ll dis,ldis; int age; il node(ll d=0,ll ld=0,int a=0):dis(d),ldis(ld),age(a){} il bool operator<(const node&d) const { return age<d.age; } }; vector<node> d[n]; int root,siz[n],fa[n]; bool ban[n]; void prsiz(int x,int d) { siz[x]=1; for(int i=head[x]; i; i=last[i]) if(!ban[to[i]]&&to[i]!=d) prsiz(to[i],x),siz[x]+=siz[to[i]]; } void gtroot(int x,int d,int t) { static int f[n]={inf}; f[x]=siz[t]-siz[x]; for(int i=head[x]; i; i=last[i]) if(!ban[to[i]]&&to[i]!=d) gtroot(to[i],x,t),f[x]=max(f[x],siz[to[i]]); if(f[x]<f[root]) root=x; } void prnode(int x,int d,ll dis) { dpd::d[root].push_back(node(dis,dbl::gtdis(x,fa[root]),age[x])); for(int i=head[x]; i; i=last[i]) { if(!ban[to[i]]&&to[i]!=d) prnode(to[i],x,dis+len[i]); } } void build(int x,int lrt) { root=0; prsiz(x,0); gtroot(x,0,x); x=root; fa[x]=lrt; ban[x]=1; prnode(x,0,0); sort(d[x].begin(),d[x].end()); d[x].push_back(node(0,0,a)); for(unsigned i=d[x].size()-2; ~i; --i) { d[x][i].dis+=d[x][i+1].dis; d[x][i].ldis+=d[x][i+1].ldis; } for(int i=head[x]; i; i=last[i]) { if(!ban[to[i]]) build(to[i],x); } } il ll query(int c,int l,int r) { vector<node>::iterator l,r; ll ans=0; for(int x=c; x; x=fa[x]) { l=lower_bound(d[x].begin(),d[x].end(),node(0,0,l)); r=upper_bound(d[x].begin(),d[x].end(),node(0,0,r)); ans+=dbl::gtdis(x,c)*(r-l)+(l->dis-r->dis); if(fa[x]) ans-=dbl::gtdis(fa[x],c)*(r-l)+(l->ldis-r->ldis); } return ans; } } int main() { scanf("%d%d%d",&n,&q,&a); for(int i=1; i<=n; ++i) scanf("%d",&age[i]); for(int x,y,w,i=n; --i; ) { scanf("%d%d%d",&x,&y,&w); addedge(x,y,w); } dbl::prdfs(1,0); dpd::build(1,0); ll lans=0; for(int u,a,b; q--; ) { scanf("%d%d%d",&u,&a,&b); a=(lans+a)%a, b=(lans+b)%a; if(a>b) swap(a,b); printf("%lld\n",lans=dpd::query(u,a,b)); } return 0; } // 代码o2需要
好了,滚去看 紫荆花之恋 了
上一篇: (办公)springboot配置全局异常
下一篇: 公司网站被黑应该怎么处理?