点分治习题

点分治

点分治步骤P3806 【模板】点分治1P3714 [BJOI2017]树的难题P4178 TreeD. Fish eating fruit 2019沈阳网络预选赛（树形DP || 点分治）

点分治步骤

每次找到一个重心，以重心为根开始分治。先 dfs1 拿前面的数据来更新答案，然后 dfs2 将当前子树的数据也更新上去。每次换一个重心的时候，都需要清空 cnt 数组。这些需要重新记录。

P3806 【模板】点分治1

链接：https://www.luogu.com.cn/problem/P3806

题意：给定一棵有 $n$ 个点的树， $m$ 个询问，询问树上距离为 k 的点对是否存在

思路：用 cnt 数组记录一下，当前 点 到根的距离。每次查询 $cnt[k[i]-dis[u]]$ 是否存在即可。

#include <bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; const int maxn=1e4+5,maxm=100+5,maxk=1e7+5; int n,m; int k[maxm],ans[maxm],sz[maxn],dis[maxn]; bool visit[maxn],cnt[maxk]; vector<pair<int,int> > e[maxn]; int rt,maxsz,sonsize; void findRoot(int u,int fa,int tot) { sz[u]=1; int cur=0; for(auto x: e[u]) { int v=x.fi; if(v==fa||visit[v]) continue; findRoot(v,u,tot); sz[u]+=sz[v]; cur=max(cur,sz[v]); } cur=max(cur,tot-sz[u]); if(cur<maxsz) maxsz=cur,rt=u; } void dfs1(int u,int fa) { sonsize++; for(int i=1; i<=m; ++i) if(dis[u]<=k[i]) ans[i]|=cnt[k[i]-dis[u]]; for(auto x: e[u]) { int v=x.fi,w=x.se; if(v==fa||visit[v]) continue; dis[v]=dis[u]+w; dfs1(v,u); } } void dfs2(int u,int fa,int f) { for(int i=1; i<=m; ++i) if(dis[u]<=k[i]) cnt[dis[u]]=f; for(auto x: e[u]) { int v=x.fi; if(v==fa||visit[v]) continue; dfs2(v,u,f); } } void dfs(int u,int fa,int tot) { maxsz=1e5; findRoot(u,fa,tot); u=rt; visit[u]=1; dis[u]=0; cnt[0]=1; for(auto x: e[u]) { int v=x.fi,w=x.se; if(visit[v]) continue; dis[v]=w; sonsize=0; dfs1(v,u); sz[v]=sonsize; dfs2(v,u,1); } dfs2(u,0,0); for(auto x: e[u]) { int v=x.fi; if(visit[v]) continue; dfs(v,u,sz[v]); } } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n-1; ++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); e[u].push_back({v,w}); e[v].push_back({u,w}); } for(int i=1; i<=m; ++i) scanf("%d",&k[i]); dfs(1,0,n); for(int i=1; i<=m; ++i) puts(ans[i]?"AYE":"NAY"); return 0; }

P3714 [BJOI2017]树的难题

链接：https://www.luogu.com.cn/problem/P3714

题意：给定一棵带有边权的树，问你通过 L 到 R 条边能够获得的最大权值是多少？

思路：可以在将前面的所有状态都放在线段树上，然后在第一次 dfs 的时候，在树上查询 $(L-depth[u],R-depth[u])$ 之间的最大距离

这里有点特殊，权值是通过不同颜色段数来计数的，所以可以开两棵线段树。一棵表示顶端的颜色相同，另一颗表示不同。然后遇到新的不同颜色时，对它们合并一下就好了 #include <bits/stdc++.h> #define fi first #define se second #define getval(rt) (rt?st[rt]:-inf) #define ll long long using namespace std; const int maxn=2e5+5,tot=2e5,inf=2e9; int n,m,L,R; int val[maxn],depth[maxn],dis[maxn],col[maxn]; int ans=-inf,sz[maxn],visit[maxn],sonsize; vector<pair<int,int> > e[maxn]; int ls[maxn*25],rs[maxn*25],st[maxn*25],no,rt1,rt2; void update(int &rt,int pos,int L,int R,int val) { if(!rt) { rt=++no; st[rt]=-inf; ls[rt]=rs[rt]=0; } if(L==R) { st[rt]=max(getval(rt),val); return; } int mid=(L+R)>>1; if(pos<=mid) update(ls[rt],pos,L,mid,val); if(pos>mid) update(rs[rt],pos,mid+1,R,val); st[rt]=max(getval(ls[rt]),getval(rs[rt])); } int merge(int rt1,int rt2) { if(!rt1||!rt2) return rt1|rt2; int rt=rt1; ls[rt]=merge(ls[rt1],ls[rt2]); rs[rt]=merge(rs[rt1],rs[rt2]); st[rt]=max(getval(ls[rt]),getval(rs[rt])); return rt; } int query(int rt,int l,int r,int L,int R) { if(!rt||l>r) return -inf; if(l<=L&&R<=r) return st[rt]; int mid=(L+R)>>1,ans=-inf; if(l<=mid) ans=max(ans,query(ls[rt],l,r,L,mid)); if(r>mid) ans=max(ans,query(rs[rt],l,r,mid+1,R)); return ans; } int maxsz,rt; void findRoot(int u,int fa,int tot) { sz[u]=1; int cur=0; for(auto x: e[u]) { int v=x.se; if(v==fa||visit[v]) continue; findRoot(v,u,tot); sz[u]+=sz[v]; cur=max(cur,sz[v]); } cur=max(cur,tot-sz[u]); if(cur<maxsz) maxsz=cur,rt=u; } void dfs1(int u,int fa,int c1) { sonsize++; if(depth[u]>=L&&depth[u]<=R) ans=max(ans,dis[u]); int l=max(0,L-depth[u]),r=R-depth[u]; ans=max(ans,dis[u]+query(rt1,l,r,0,tot)); ans=max(ans,dis[u]+query(rt2,l,r,0,tot)-val[c1]); for(auto x: e[u]) { int v=x.se,c=x.fi; if(v==fa||visit[v]) continue; col[v]=c; depth[v]=depth[u]+1; dis[v]=dis[u]+(col[v]==col[u]?0:val[c]); dfs1(v,u,c1); } } void dfs2(int u,int fa) { update(rt2,depth[u],0,tot,dis[u]); for(auto x: e[u]) { int v=x.se; if(v==fa||visit[v]) continue; dfs2(v,u); } } void dfs(int u,int fa,int tot) { maxsz=1e9; findRoot(u,fa,tot); u=rt; visit[u]=1; int last=inf; no=rt1=rt2=0; for(auto x: e[u]) { int v=x.se,c=x.fi; if(visit[v]) continue; if(last!=inf&&last!=c) { rt1=merge(rt1,rt2); rt2=0; } last=c; sonsize=0; col[v]=c; dis[v]=val[c],depth[v]=1; dfs1(v,u,c); sz[v]=sonsize; dfs2(v,u); } for(auto x: e[u]) { int v=x.se; if(visit[v]) continue; dfs(v,u,sz[v]); } } int main() { scanf("%d%d%d%d",&n,&m,&L,&R); for(int i=1; i<=m; ++i) scanf("%d",&val[i]); for(int i=1; i<=n-1; ++i) { int u,v,c; scanf("%d%d%d",&u,&v,&c); e[u].push_back({c,v}); e[v].push_back({c,u}); } for(int i=1; i<=n; ++i) sort(e[i].begin(),e[i].end()); dfs(1,0,n); printf("%d\n",ans); return 0; }

P4178 Tree

链接：https://www.luogu.com.cn/problem/P4178

题意：给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。

思路：

点分治时，开一棵权值线段树，标记当前距离的树的数量，然后就区间查询 $[0,k-dis[u]]$ 的点的数量即可。注意每次换根，都需要将线段树清空 #include <bits/stdc++.h> #define fi first #define se second #define ls (rt<<1) #define rs (rt<<1|1) #define ll long long using namespace std; const int maxn=4e4+5,N=2e4; int n,k; vector<pair<int,int> > e[maxn]; int visit[maxn],dis[maxn]; ll ans=0; int st[N<<2]; void build(int rt,int L,int R) { st[rt]=0; if(L==R) return; int mid=(L+R)>>1; build(ls,L,mid); build(rs,mid+1,R); } void update(int rt,int pos,int L,int R,int f) { st[rt]+=f; if(L==R) return; int mid=(L+R)>>1; if(pos<=mid) update(ls,pos,L,mid,f); if(pos>mid) update(rs,pos,mid+1,R,f); } int query(int rt,int l,int r,int L,int R) { if(l<=L&&R<=r) return st[rt]; int mid=(L+R)>>1; int ans=0; if(l<=mid) ans+=query(ls,l,r,L,mid); if(r>mid) ans+=query(rs,l,r,mid+1,R); return ans; } int maxsz,rt,sonsize,sz[maxn]; void findRoot(int u,int fa,int tot) { sz[u]=1; int cur=0; for(auto x: e[u]) { int v=x.fi; if(v==fa||visit[v]) continue; findRoot(v,u,tot); sz[u]+=sz[v]; cur=max(cur,sz[v]); } cur=max(cur,tot-sz[u]); if(cur<maxsz) maxsz=cur,rt=u; } void dfs1(int u,int fa) { sonsize++; if(k-dis[u]>=0) ans+=query(1,0,k-dis[u],0,N); for(auto x: e[u]) { int v=x.fi,w=x.se; if(v==fa||visit[v]) continue; dis[v]=dis[u]+w; dfs1(v,u); } } void dfs2(int u,int fa,int f) { if(dis[u]<=N) update(1,dis[u],0,N,f); for(auto x: e[u]) { int v=x.fi; if(v==fa||visit[v]) continue; dfs2(v,u,f); } } void dfs(int u,int fa,int tot) { maxsz=1e9; findRoot(u,fa,tot); u=rt; visit[u]=1; for(auto x: e[u]) { int v=x.fi,w=x.se; if(visit[v]) continue; dis[v]=w; sonsize=0; dfs1(v,u); sz[v]=sonsize; dfs2(v,u,1); } for(auto x: e[u]) { int v=x.fi,w=x.se; if(visit[v]) continue; dfs2(v,u,-1); } for(auto x: e[u]) { int v=x.fi,w=x.se; if(visit[v]) continue; dfs(v,u,sz[v]); } } int main() { scanf("%d",&n); for(int i=1; i<=n-1; ++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); e[u].push_back({v,w}); e[v].push_back({u,w}); } scanf("%d",&k); update(1,0,0,N,1); dfs(1,0,n); printf("%lld\n",ans); return 0; }

D. Fish eating fruit 2019沈阳网络预选赛（树形DP || 点分治）

链接：https://www.jisuanke.com/contest/3007/challenges

题意：给定一棵树求所有点对，模3意义下的总边权值之和。 思路：点分治，用 cnt 记录路径数，sum记录路径和。

#include <bits/stdc++.h> #define fi first #define se second #define ll long long using namespace std; const int maxn=1e4+5,mod=1e9+7; int n; ll cnt[3],ans[3],sum[3]; int dis[maxn]; vector<pair<int,int> > e[maxn]; bool visit[maxn]; int maxsz,rt,sz[maxn]; void findRoot(int u,int fa,int tot) { sz[u]=1; int cur=0; for(auto x: e[u]) { int v=x.fi; if(v==fa||visit[v]) continue; findRoot(v,u,tot); sz[u]+=sz[v]; cur=max(cur,sz[v]); } cur=max(cur,tot-sz[u]); if(cur<maxsz) maxsz=cur,rt=u; } int sonsz; void dfs1(int u,int fa) { sonsz++; for(int i=0; i<=2; ++i) { int pos=(i+dis[u])%3; ans[pos]=(1ll*ans[pos]+1ll*cnt[i]*dis[u]%mod+sum[i])%mod; } for(auto x: e[u]) { int v=x.fi,w=x.se; if(v==fa||visit[v]) continue; dis[v]=dis[u]+w; dfs1(v,u); } } void dfs2(int u,int fa,int f) { cnt[dis[u]%3]+=f; (sum[dis[u]%3]+=dis[u]*f)%=mod; for(auto x: e[u]) { int v=x.fi,w=x.se; if(v==fa||visit[v]) continue; dfs2(v,u,f); } } void dfs(int u,int fa,int tot) { maxsz=1e9; findRoot(u,fa,tot); u=rt; visit[u]=1; for(auto x: e[u]) { int v=x.fi,w=x.se; if(visit[v]) continue; sonsz=0; dis[v]=w; dfs1(v,u); sz[v]=sonsz; dfs2(v,u,1); } for(auto x: e[u]) { int v=x.fi,w=x.se; if(visit[v]) continue; dfs2(v,u,-1); } for(auto x: e[u]) { int v=x.fi; if(visit[v]) continue; dfs(v,u,sz[v]); } } int main() { while(~scanf("%d",&n)) { for(int i=1; i<=n; ++i) e[i].clear(),visit[i]=0; for(int i=0; i<=2; ++i) ans[i]=cnt[i]=sum[i]=0; for(int i=1; i<=n-1; ++i) { int u,v,w; scanf("%d%d%d",&u,&v,&w); u++,v++; e[u].push_back({v,w}); e[v].push_back({u,w}); } cnt[0]=1; dfs(1,0,n); for(int i=0; i<=2; ++i) printf("%lld%c",ans[i]*2%mod,i==2?'\n':' '); } return 0; }